Indexed Tree/권영기

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;
}