[Spoj] PSEGTREE - Make Versions in Segment Tree

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : PSEGTREE - Make Versions in Segment Tree
Source            : Spoj
Category          : Data Structure
Algorithm         : Persistent Segment Tree
Verdict           : Accepted  

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <memory.h>
#include <functional>
#include <numeric>
 
using namespace:: std;
 
 
#define READ                                 freopen("in.txt", "r", stdin)
#define WRITE                                freopen("out.txt", "w", stdout)
 
#define FAST                                 ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
 
 
 
#define All(v)                               v.begin(), v.end()
#define SZ(a)                                a.size()
#define Sort(v)                              sort(All(v))
#define ED(v)                                Sort(v), v.erase(unique(All(v), v.end())
#define Common(a, b)                         Sort(v), Sort(b), a.erase(set_intesection(All(a), All(b), a.begin(), a.end()))
#define UnCommon(a, b)                       Sort(v), Sort(b), a.erase(set_symmetric_difference(All(a), All(b), All(a)))
 
 
#define max3(a, b, c)                        max(a, max(b, c))
#define min3(a, b, c)                        min(a, min(b, c))
#define maxAll(v)                            *max_element(All(v))
#define minAll(v)                            *min_element(All(v))
 
 
#define AllUpper(a)                          transform(All(a), a.begin(), :: toupper)
#define AllLower(a)                          transform(All(a), a.begin(), :: tolower)
#define Rev(a)                               reverse(All(a))
 
 
#define memo(a, b)                           memset(a, b, sizeof(a))
 
#define ff                                   first
#define ss                                   second
#define pb                                   push_back
#define mk                                   make_pair
 
#define inf2                                 1 << 28
 
template <typename T>string toString (T Number)    { stringstream st; st << Number; return st.str(); }
int toInteger (string s)                           { int p; istringstream st(s); st>>p ; return p; }
 
 
 
//int dr[] = {1, -1, 0, 0};               // 4 Direction
//int dc[] = {0, 0, 1, -1};
 
//int dr[] = {0, 0, 1, -1, 1, 1, -1, -1};  // 8 Direction
//int dc[] = {1, -1, 0, 0, 1, -1, 1, -1};
 
//int dr[] = {-1, 1, -2, -2, -1, 1, 2, 2}; // knight Moves
//int dc[] = {-2, -2, -1, 1, 2, 2, 1, -1};
 
 
#define Exp                                  exp(1.0)
#define PIE                                  2*acos(0.0)
#define Sin(a)                               sin(((a)*PI)/180.0)
#define mod                                  1000000007
#define EPS                                  1e-9
 
#define sqr(a)                               ((a)*(a))
#define gcd(a,b)                              __gcd(a,b)
#define lcm(a,b)                             (a*(b/gcd(a,b)))
 
 
typedef long long                            ll;
 
const int mx = 100000 + 5;
 
struct node 
{
       int val; 
       node* left;
       node* right; 
       node() {}
       node(node* _left, node* _right, int _val) 
       {
             val = _val;
             left = _left;
             right = _right;
       }
} *version[mx * 2];
 
 
int arr[mx * 2];
 
void build(node* n, int low, int high)
{
      if (low == high)
      {
             n->val = arr[low];
             return;
      }
      int mid = (low + high) >> 1;
      n->left = new node(NULL, NULL, 0);
      n->right = new node(NULL, NULL, 0);
      build(n->left, low, mid);
      build(n->right, mid+1, high);
      n->val = n->left->val + n->right->val;
}
 
void update1(node* n, int low, int high, int idx, int val)
{
      if (idx > high || idx < low || low > high) return;
      if (low == high)
      {
            n->val += val;
            return;
      }
      int mid = (low + high) >> 1;
      if (idx <= mid)
      {
            update1(n->left, low, mid, idx, val);
      }
      else
      {
            update1(n->right, mid+1, high, idx, val);
      }
      n->val = n->left->val + n->right->val;
}
 
void update2(node* prev, node* cur, int low, int high, int idx, int val)
{
      if (idx > high || idx < low || low > high) return;
      if (low == high)
      {
            cur->val = prev->val + val;
            return;
      }
      int mid = (low + high) >> 1;
      if (idx <= mid)
      {
            cur->right = prev->right;
            cur->left = new node(NULL, NULL, 0);
            update2(prev->left, cur->left, low, mid, idx, val);
      }
      else
      {
            cur->left = prev->left;
            cur->right = new node(NULL, NULL, 0);
            update2(prev->right, cur->right, mid+1, high, idx, val);
      }
      cur->val = cur->left->val + cur->right->val;
}
 
int query(node* n, int low, int high, int i, int j)
{
      if (i>high || j<low || low > high || n == NULL) return 0;
      if (low >= i && high <= j) return n->val;
      int mid = (low + high) >> 1;
      int p1 = query(n->left, low, mid, i, j);
      int p2 = query(n->right, mid+1, high, i, j);
      return p1 + p2;
}
 
int main()
{
      //READ;
      FAST;
 
      int n;
      cin >> n;
      for (int i = 1; i <= n; i++) cin >> arr[i];
      version[0] = new node(NULL, NULL, 0);
      build(version[0], 1, n);
      int q;
      cin >> q;
      int k = 0;
      while (q--)
      {
            int type;
            cin >> type;
            if (type == 1)
            {
                  k++;
                  int v_idx, pos, v;
                  cin >> v_idx >> pos >> v;
                  version[k] = new node(NULL, NULL, 0);
                  update2(version[v_idx], version[k], 1, n, pos, v);
            }
      }
      else
      {
            int v_idx, l, r;
            cin >> v_idx >> l >> r;
            cout << query(version[v_idx], 1, n, l, r) << endl;
      }
  }
  return 0;
}