Segment Tree


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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s