Segment Tree

0

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <sstream>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <map>

#define ll long long
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)

#define MAX 1000
using namespace std;

int ara[MAX];
int tree[MAX*3];

void init(int node,int b,int e)
{
if(b==e)
{
tree[node]=ara[b];
return;
}
int mid=(b+e)/2;
int left=2*node;
int right=2*node+1;
init(left,b,mid);
init(right,mid+1,e);
tree[node]=tree[left]+tree[right];
}

int query(int node,int b,int e,int i, int j)
{
if(i>e || j<b)
return 0;
if(b>=i && e<=j)
return tree[node];
int left=node*2;
int right=node*2+1;
int mid=(b+e)/2;
int p1=query(left,b,mid,i,j);
int p2=query(right,mid+1,e,i,j);
return p1+p2;
}

void update(int node,int b,int e, int i, int new_value)
{
if(i>e || i<b)
return;
if(b>=i && e<=i)
{
tree[node]=new_value;
return;
}
int left=node*2;
int right=node*2+1;
int mid=(b+e)/2;
update(left,b,mid,i,new_value);
update(right,mid+1,e,i,new_value);
tree[node]=tree[left]+tree[right];
}

int main()
{
freopen("in.txt","r",stdin);
///freopen("out.txt","w",stdout);
int n;
cin>>n;
for(int i=1; i<=n; i++)
cin>>ara[i];
init(1,1,n);
cout<<query(1,1,n,1,4)<<endl;
update(1,1,n,2,0);
cout<<query(1,1,n,2,2)<<endl;
update(1,1,n,2,1);
cout<<query(1,1,n,2,3)<<endl;
return 0;
}

Binary Indexed Tree (BIT)

0

#include <bits/stdc++.h>

using namespace std;

int a[100000],tree[100000];

int query(int idx)
{
int sum=0;
while(idx>0)
{
sum+=tree[idx];
idx -= idx & (-idx);
}
return sum;
}

void update(int idx, int x, int n)
{
while(idx<=n)
{
tree[idx]+=x;
idx += idx & (-idx);
}
}

int main ()
{
int tc,n,q,cas=0;
cin>>tc;
while(tc--)
{
printf("Case %d:\n",++cas);
cin>>n>>q;
memset(tree,0,sizeof tree);
for(int i=1; i<=n; i++)
{
cin>>a[i];
update(i,a[i],n);
}
int ic,idx,v,x,y;
for(int i=0; i<q; i++)
{
cin>>ic;
if(ic==1)
{
cin>>idx;
idx++;
update(idx,-a[idx],n);
printf("%d\n",a[idx]);
a[idx]=0;
}

else if(ic==2)
{
cin>>idx>>v;
idx++;
update(idx,v,n);
a[idx]+=v;
}

else
{
cin>>x>>y;
printf("%d\n",query(y+1)-query(x));
}
}

}
return 0;
}