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