Segment_Tree_C++

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace   std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

typedef pair<int, int> pii; typedef long long ll; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vii; typedef vector<pll> vll;
typedef map<ll, ll> mii; typedef map<string, ll> msi; typedef vector< vi > vvi;

#define     sz                 size()
#define     pb                 push_back
#define     inf                (1<<30)
#define     mod                (1000000007)
#define     pi                 (acos(-1.0))
#define     mem(a,b)           memset((a), (b), sizeof(a));
#define     fast_io            ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     what_is(x)         cerr << #x << " is " << x << endl;
#define     rep(i, n)          for(__typeof(n) i=0; i<(n); i++)
#define     foab(i, a, b)      for(__typeof(b) i=(a); i<=(b); i++)
#define     foba(i, a, b)      for(__typeof(b) i=(b); i>=(a); i--)
#define     foch(it, l)        for(__typeof((l).begin()) it = begin(l);  it != end(l); it++)
#define     d_value(x)         cout<<fixed<<setprecision(x);
#define     file_io            {                                        \
                                    freopen("input.txt", "r", stdin);   \
                                    freopen("output.txt", "w", stdout); \
                               }
#define error(args...) {                                                            \
        string _s = #args; replace(_s.begin(), _s.end(), ',', ' ');                 \
        stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);    \
        }

void err(istream_iterator<string> it) {}                 template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) { cerr << *it << " = " << a << endl; err(++it, args...); }

/**Define BitWise operation**/
#define     checkBit(n, pos)            (n & (1<<(pos)))
#define     bitOn(n, pos)               (n | (1<<(pos)))
#define     bitOff(n, pos)              (n & ~(1<<(pos)))
inline void printBits(int n){ if(n >= 2)printBits(n/2); cout<<(n&1); }
inline int countOnes(int n) { int r=0; while(n && ++r) n -= n&(-n); return r; }
inline int bigMod(ll a, ll b, int M) { int r = (int)(a % M), v = 1; while(b){if(b % 2 == 1)v = (v * r) % M; r = (r * r) % M; b/=2;} return v; }

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
string toString(T n) { stringstream ss; ss << n; return ss.str(); }
template< typename T >
T e_gcd(T a, T b, T& x, T& y) {
    if(!a){ x = 0, y = 1; return b; }
    T x1, y1, gcd = e_gcd<T>(b%a, a, x1, y1);
    x = y1 - (b/a)*x1, y = x1;
    return gcd;
}
template< typename T >
inline T modInverse(T a, T m){ T x, y; T g = e_gcd<T>(a, m, x, y); if(g != 1){ return -1; } else{ return (x%m + m)%m; } }
template<typename T> ostream&
operator<<(ostream& os, const vector<T> &t) { ll n = t.size(); rep(i, n) os<<t[i]<<" "; return os; }
template<typename T,typename TT>
ostream& operator<<(ostream &os, const pair<T,TT> &t) { return os<<"("<<t.first<<","<<t.second<<")"; }

enum COLOR{ white=1 , grey=2 , black=3, red = 4, green = 5, blue = 6 };

vii dir_4 {{1,0}, {0,1}, {-1,0}, {0,-1}};
vii dir_8 {{0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}};
vii dir_knight {{2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1}};
//-------------- ---------------- ----------------- --------------- ------------ ----------


//This is a Segment Tree Data structure for Range Query, Point Update
class SegmentTree{
    int* ara, *tree;
public:

    explicit SegmentTree(int n, const int _ara[]){
        ara = new int[n+1], tree = new int[4*n+1];
        foab(i, 1, n){
            ara[i] = _ara[i-1];
        }
    }

    void init(const int& pos, const int& begin, const int& end){
        if(begin == end){//leaf node
            tree[pos] = ara[end];
        }else{//internal node
            init(pos<<1, begin, (begin+end)>>1);
            init((pos<<1)+1, ((begin+end)>>1)+1, end);
            tree[pos] = tree[pos<<1] + tree[(pos<<1)+1];
        }
    }

    void update(const int& pos, const int& begin, const int& end, const int& indx, const int& newVal){
        if(end < indx || indx < begin){//out of boundary
            return;
        }else if(indx<=begin && indx>=end){//relevant segment(index)
            tree[pos] = newVal;
        }else{//partial overlap
            update(pos<<1, begin, (begin+end)>>1, indx, newVal);
            update((pos<<1)+1, ((begin+end)>>1)+1, end, indx, newVal);
            tree[pos] = tree[pos<<1] + tree[(pos<<1)+1];
        }
    }

    int query(const int& pos, const int& begin, const int& end, const int& i, const int& j){
        if(i<=begin && end<=j){//relevant segment
            return tree[pos];
        }else if(j<begin || i>end){//out of boundary
            return 0;
        }else{//partial overlap
            return query(pos<<1, begin, (begin+end)>>1, i, j) + query((pos<<1)+1, ((begin+end)>>1)+1, end, i, j);
        }
    }

    virtual ~SegmentTree(){
        delete [] ara;
        delete [] tree;
        ara = tree = nullptr;
    }
};


int main(int argc, char** argv) {
    //d_value(20);
    fast_io

    int n = 4, ara[] = {1, 0, 3, 4};
    SegmentTree segmentTree(n, ara);
    segmentTree.init(1, 1, 4);
    segmentTree.print();
    cout<<segmentTree.query(1, 1, 4, 1, 4)<<endl;
    segmentTree.update(1, 1, 4, 2, 2);
    segmentTree.print();
    cout<<segmentTree.query(1, 1, 4, 1, 4)<<endl;

    return 0;
}