Segment Tree Source Code

Tutorial : http://www.shafaetsplanet.com/planetcoding/?p=1557


#include<bits/stdc++.h>

#define mx 100001

using namespace std;


int arr[mx];
int tree[mx*4];


void init(int node, int b,int e)
{
    if(b==e)
    {
        tree[node]=arr[b];
        return;
    }

    int left=2*node;
    int right=(2*node )+1;

    int mid=(b+e)/2;

    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(j<b || i>e) return 0;

    if(b>=i && e<=j)
    {
        return tree[node];
    }

    int left=2*node;
    int right=(2*node)+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 val)
{
    if(i<b || i>e) return;

    if(b==e)
    {
        tree[node]=val;
        return;
    }

    int left=2*node;
    int right=(2*node)+1;
    int mid=(b+e)/2;

    update(left,b,mid,i,val);
    update(right,mid+1,e,i,val);

    tree[node]=tree[left]+tree[right];
}

int main()
{
    int n;
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&arr[i]);
    }

    init(1,1,n);

    cout<<query(1,1,n,3,7)<<endl;
    update(1, 1, n, 2, 2);
    cout << query(1, 1, n, 1, 2) << endl;
}