Segment Tree

যে কাজে ব্যবহার করা যায় : 

এটি দিয়ে কোন একটা array এর একটা ইনডেক্স থেকে অন্য ইনডেক্স এর মাঝের value গুলোর যোগফল বের করা যায় । if( i<j) sum=a[i] + ..... + a[j].

এটি দিয়ে কোন ইনডেক্স এর  value change বা add করে পুনরায় একটা ইনডেক্স থেকে অন্য ইনডেক্স এর মাঝের value গুলোর যোগফল বের করা যায় । 

......................................................................................................................................................................................................................................................................................................................................

শুরু : 

#include<bits/stdc++.h>
using namespace std;
#define max 10000
int arr[max];
int tree[3*max];
int a,b;
void segtree(int node,int l,int r)
{
    if(l==r)
    {
        tree[node]=arr[l];
        return;
    }
    int Left=node*2;
    int Right=node*2+1;
    int mid=(l+r)/2;
    segtree(Left,l,mid);
    segtree(Right,mid+1,r);
    tree[node]=tree[Left]+tree[Right];
}
long read(int node,int l,int r)
{
    if(l>b||r<a)//over bundory
    return 0;
    if(l>=a&&r<=b)
    return tree[node];

    int Left=node*2;
    int Right=node*2+1;
    int mid=(l+r)/2;

    int p1=read(Left,l,mid);
    int p2=read(Right,mid+1,r);
    return p1+p2;
}

void update(int node,int l,int r,int p,int val)//add value of a position
{
    tree[node]+=val;
    if(l==r)
    return;
    int Left=node*2;
    int Right=node*2+1;
    int mid=(l+r)/2;
    if(p>=l&&p<=mid)
    update(Left,l,mid,p,val);
    else
    update(Right,mid+1,r,p,val);
}
void update1(int node,int l,int r,int p,int newval) // new value of a position
{
if (p > r || p < l) return;
if (l >= p && r <= p) {
tree[node]=newval;
return;
}
int Left=node*2;
int Right=node*2+1;
int mid=(l+r)/2;
update1(Left,l,mid,p,newval);
update1(Right,mid+1,r,p,newval);
tree[node]=tree[Left]+tree[Right];
}
int main()
{
    int n,i,value,position;
    cin>>n;
    for(i=1;i<=n;i++)
    cin>>arr[i];

    segtree(1,1,n);
    cin>>a>>b;//sum of range a to b
    cout<<read(1,1,n)<<endl;

    cin>>position>>value; // position a value add .
    update(1,1,n,position,value);
    cin>>a>>b;//sum of range a to b
    cout<<read(1,1,n)<<endl;

    cin>>position>>value;  // position a value change .
    update1(1,1,n,position,value);
    cin>>a>>b;//sum of range a to b
    cout<<read(1,1,n)<<endl;
    return 0;
}

Binary Index Tree

যে কাজে ব্যবহার করা যায় :
যেকোন position update করা যায় ।
i থেকে  j ইন্ডেক্স এর যোগফল বের করা যায় । ( i<j )

......................................................................................................................................................................................................................................................................................................................................

শুরু :

#include<bits/stdc++.h>
using namespace std;
#define MaxVal 100007
int tree[MaxVal+1];
int read(int idx)
{
    int sum=0;
    while(idx>0)
    {
        sum+=tree[idx];
        idx-=(idx & -idx);
    }
    return sum;
}
void update(int idx,int val)
{
    while(idx<=MaxVal)
    {
        tree[idx]+=val;
        idx+=(idx & -idx);
    }
}

int main()
{
    int a,b,p,q,value,ans;

    for(int i=1;i<=5;i++)
    {
        scanf("%d%d",&a,&value);
        update(a,value);
    }
    for(int i=1;i<=2;i++)
    {
        scanf("%d%d",&a,&b);
        ans=read(b)-read(a-1);
        printf("%d ",ans);
    }
    return 0;
}