LightOJ 1112 - Curious Robin Hood

Reference: শাফায়াতের ব্লগ

//Next Codeforces Round #354 (Div. 2)
#include<bits/stdc++.h>

//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<cstring>
//#include<cmath>
//#include<map>

using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define high 100005
//#define i64 long long

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;

int ar[high];
LL tree[high * 3];

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

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

    build(left , b , mid);
    build(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 or j < b) return 0;

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

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

    int pek = query(left, b , mid, i , j);
    int pdui = query(right, mid + 1, e , i , j);

    return pek + pdui;
}

void update(int node, int b , int e, int i, int newvalue)
{
    if(i > e or i < b) return;

    if(b >= i and e <= i)
    {
        tree[node] = newvalue;

        return;
    }

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

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

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

int main()
{
    int t , tc=0 , n , q , i , x , k , j , p , ans;
    sf("%d", &t);
    while(t--)
    {
        sf("%d %d", &n , &q);

        for(p=1; p<=n; p++)
        {
            sf("%d", &ar[p]);
        }

        build(1, 1, n);

        pf("Case %d:\n", ++tc);

        while(q--)
        {
            sf("%d", &k);

            if(k == 1)
            {
                sf("%d", &x);
                pf("%d\n", ar[x+1]);
                ar[x+1]=0;
                //updateone(1, 1, n , x+1, 0);
                update(1 , 1 , n , x+1, 0);
            }

            else if(k == 2)
            {
                sf("%d %d", &i , &x);
                ar[i+1]+=x; // make the change
                update(1, 1, n, i+1, ar[i+1]); // make the change
            }

            else if(k == 3)
            {
                sf("%d %d", &i, &j);
                ans = query(1, 1, n, i+1 , j+1);
                pf("%d\n", ans);
            }
        }
    }

    return 0;
}