No difference found
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;
}
