Maintenance script: Repair batch-0002 pages from live compare

2026-03-27T00:16:05Z

Repair batch-0002 pages from live compare

← Older revision		Revision as of 00:16, 27 March 2026
Line 35:		Line 35:

	if(current->level == limit){		if(current->level == limit){
	current->item = items[*count];		current->item = items[*count];
	(*count)++;		(*count)++;
	}		}
Line 77:		Line 77:
	int n;		int n;
	scanf("%d", &n);		scanf("%d", &n);
	int items[N];		int items[N];
	for(int i = 0; i<n; i++){		for(int i = 0; i<n; i++){
	scanf("%d", &items[i]);		scanf("%d", &items[i]);
	}		}
	int level = 0;		int level = 0;
Line 108:		Line 108:
	idx = i;		idx = i;
	while(idx <= *n){		while(idx <= *n){
	tree[idx] += f[i];		tree[idx] += f[i];
	idx += (idx & -idx);		idx += (idx & -idx);
	}		}
Line 117:		Line 117:
	temp = ep;		temp = ep;
	while(temp > 0){		while(temp > 0){
	sum1 += tree[temp];		sum1 += tree[temp];
	temp -= (temp & -temp);		temp -= (temp & -temp);
	}		}
	temp = sp-1;		temp = sp-1;
	while(temp > 0){		while(temp > 0){
	sum2 += tree[temp];		sum2 += tree[temp];
	temp -= (temp & - temp);		temp -= (temp & - temp);
	}		}
Line 129:		Line 129:
	void update_BinaryIndexedTree(int tree, int address, int item, int n)		void update_BinaryIndexedTree(int tree, int address, int item, int n)
	{		{
	int temp = tree[address] - item;		int temp = tree[address] - item;
	while(address <= *n){		while(address <= *n){
	tree[address] += temp;		tree[address] += temp;
	address += (address & -address);		address += (address & -address);
	}		}
Line 141:		Line 141:

	int n;		int n;
	int f[N];		int f[N];
	int tree[N];		int tree[N];
	scanf("%d", &n);		scanf("%d", &n);

	for(int i = 0; i<n; i++){		for(int i = 0; i<n; i++){
	scanf("%d", &f[i+1]);		scanf("%d", &f[i+1]);
	tree[i+1] = 0;		tree[i+1] = 0;
	}		}

Line 176:		Line 176:
	temp = ep;		temp = ep;
	while(temp > 0){		while(temp > 0){
	sum1 += tree[temp];		sum1 += tree[temp];
	temp -= (temp & -temp);		temp -= (temp & -temp);
	}		}
	temp = sp-1;		temp = sp-1;
	while(temp > 0){		while(temp > 0){
	sum2 += tree[temp];		sum2 += tree[temp];
	temp -= (temp & -temp);		temp -= (temp & -temp);
	}		}
Line 188:		Line 188:
	void IndexedTree::update(int address, int item, int key){		void IndexedTree::update(int address, int item, int key){
	int temp;		int temp;
	if(key == 1)temp = item - tree[address];		if(key == 1)temp = item - tree[address];
	else temp = item;		else temp = item;
	while(address < N){		while(address < N){
	tree[address] += temp;		tree[address] += temp;
	address += (address & -address);		address += (address & -address);
	}		}
	}		}
	IndexedTree::IndexedTree(int *f, int n){		IndexedTree::IndexedTree(int *f, int n){
	tree = new int[n + 10];		tree = new int[n + 10];
	memset(tree, 0, sizeof(int) * (n+10));		memset(tree, 0, sizeof(int) * (n+10));
	N = n;		N = n;
	for(int i = 1; i<=n; i++){		for(int i = 1; i<=n; i++){
	update(i, f[i], 0);		update(i, f[i], 0);
	}		}
	}		}
Line 208:		Line 208:
	freopen("input.txt","r",stdin);		freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);		freopen("output.txt","w",stdout);
	int n, f[100];		int n, f[100];
	cin>>n;		cin>>n;
	for(int i = 0; i<n; i++){		for(int i = 0; i<n; i++){
	cin>>f[i+1];		cin>>f[i+1];
	}		}
	IndexedTree *it = new IndexedTree(f, n);		IndexedTree *it = new IndexedTree(f, n);
Line 218:		Line 218:
	return 0;		return 0;
	}		}

imported>trailblaze at 22:33, 7 September 2012

2012-09-07T22:33:42Z

New page

IndexedTree

#include<iostream>
#include<cmath>
#define max(s, w) ((s>w)?(s):(w))
#define N 100020
struct node{
int level;
int item;
node *left, *right;

};
struct Indexed_tree{
node *root;
int count;
};
Indexed_tree it;
int find(node *current, int sp, int ep, int st, int ed)
{

if(sp == st && ep == ed)return current->item;

if(ep <= (st+ed)/2){
return find(current->left, sp, ep, st, (st+ed)/2);
}
else if(sp > (st+ed)/2){
return find(current->right, sp, ep, (st+ed)/2 + 1, ed);
}
else if(sp <= (st + ed)/2 && ed > (st+ed)/2){
return find(current->left, sp, (st+ed)/2, st, (st+ed)/2) + find(current->right, (st+ed)/2 + 1, ep, (st+ed)/2 + 1, ed);
}
}
void Init_IndexedTree(node *current, int limit, int *count, int *items){
if(*count >= N)return;

if(current->level == limit){
current->item = items[*count];
(*count)++;
}
else{
node *temp = (node *)malloc(sizeof(node));
temp->level = current->level + 1;
current->left = temp;

Init_IndexedTree(current->left, limit, count, items);

temp = (node *)malloc(sizeof(node));
temp->level = current->level + 1;
current->right = temp;

Init_IndexedTree(current->right, limit, count, items);

current->item = current->right->item + current->left->item;
}
return;
}
void insert_item(node *current, int item, const int address, int st, int end, const int *count, const int *level){
if(address == (st + end)/2 && current->level == *level){
current->item = item;
}
else if(address <= (st + end)/2){
insert_item(current->left, item, address, st, (st+end)/2, count, level);
current->item = current->left->item + current->right->item;
}
else{
insert_item(current->right, item, address, (st+end)/2 + 1, end, count, level);
current->item = current->left->item + current->right->item;
}
return;
}

int main(void)
{
freopen("input.txt","r",stdin);
freopen("output.txt","w", stdout);

int n;
scanf("%d", &n);
int items[N];
for(int i = 0; i<n; i++){
scanf("%d", &items[i]);
}
int level = 0;
it.count = 0;
it.root = (node *)malloc(sizeof(node));
it.root->level = 0;
while(1){
if(pow((double)2, level) >= n){
break;
}
level++;
}
const int maxcount = pow((double)2, level);
Init_IndexedTree(it.root, level, &it.count, items);
insert_item(it.root, 9, 2, 1, 100000, &maxcount, &level);

printf("%d", find(it.root, 2, 8, 1, maxcount));

}

BinaryIndexedTree

#include<iostream>
#define N 100
void init_BinaryIndexedTree(int *tree, int *f, int *n){
int idx, i;
for(i = 1; i<=*n; i++){
idx = i;
while(idx <= *n){
tree[idx] += f[i];
idx += (idx & -idx);
}
}
}
int read_BinaryIndexedTree(int *tree, int sp, int ep){
int temp, sum1 = 0, sum2 = 0;
temp = ep;
while(temp > 0){
sum1 += tree[temp];
temp -= (temp & -temp);
}
temp = sp-1;
while(temp > 0){
sum2 += tree[temp];
temp -= (temp & - temp);
}
return sum1 - sum2;
}
void update_BinaryIndexedTree(int *tree, int address, int item, int *n)
{
int temp = tree[address] - item;
while(address <= *n){
tree[address] += temp;
address += (address & -address);
}
}
int main(void)
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

int n;
int f[N];
int tree[N];
scanf("%d", &n);

for(int i = 0; i<n; i++){
scanf("%d", &f[i+1]);
tree[i+1] = 0;
}

int idx;
init_BinaryIndexedTree(tree, f, &n);
printf("%d", read_BinaryIndexedTree(tree, 3, 7));

}

BinaryIndexedTree C++연습
#include<iostream>
using namespace std;
class IndexedTree{

private:
int *tree;
int N;

public:
IndexedTree(int *f, int n);
int read(int sp, int ep);
void update(int address, int item, int key);
};
int IndexedTree::read(int sp, int ep)
{
int temp, sum1, sum2;
sum1 = sum2 = 0;
temp = ep;
while(temp > 0){
sum1 += tree[temp];
temp -= (temp & -temp);
}
temp = sp-1;
while(temp > 0){
sum2 += tree[temp];
temp -= (temp & -temp);
}
return sum1 - sum2;
}
void IndexedTree::update(int address, int item, int key){
int temp;
if(key == 1)temp = item - tree[address];
else temp = item;
while(address < N){
tree[address] += temp;
address += (address & -address);
}
}
IndexedTree::IndexedTree(int *f, int n){
tree = new int[n + 10];
memset(tree, 0, sizeof(int) * (n+10));
N = n;
for(int i = 1; i<=n; i++){
update(i, f[i], 0);
}
}
int main(void)
{

freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int n, f[100];
cin>>n;
for(int i = 0; i<n; i++){
cin>>f[i+1];
}
IndexedTree *it = new IndexedTree(f, n);
cout<<it->read(2, 7);

return 0;
}

IndexedTree/권영기 - Revision history

Maintenance script: Repair batch-0002 pages from live compare

imported>trailblaze at 22:33, 7 September 2012