RangeSumQuery_SegmentTree.cpp

// static RangeSumQuery using segment trees //
#include<bits/stdc++.h>

using namespace std;

void ConstructTree(long long int input[], long long int segTree[],long long int low,long long int high,long long int pos){
    if(low == high){
        segTree[pos] = input[low];
        return;
    }
    int mid = (low+high)/2;
    ConstructTree(input, segTree, low, mid, 2*pos + 1);
    ConstructTree(input, segTree, mid+1, high, 2*pos + 2);
    segTree[pos] = segTree[2*pos+1] + segTree[2*pos+2];
}

long long int rangeSumQuery(long long int segTree[],long long int qlow,long long int qhigh,long long int low,long long int high,long long int pos){
    // case of total overlap
    if(qlow <= low && qhigh >= high){
        return segTree[pos];
    }
    // case of no overlap
    if(qlow > high || qhigh < low){
        return 0;
    }
    // case of partial overlap
    long long int mid = (low+high)/2;
    return (rangeSumQuery(segTree, qlow, qhigh, low, mid, 2*pos+1) + rangeSumQuery(segTree, qlow, qhigh, mid+1, high, 2*pos+2));
}
int main()
{
    long long int n = 10;
    long long int a[n] = {1,2,3,4,5,6,7,8,1,0};
    long long int segTree[4*n+1] = {0};
    ConstructTree(a, segTree, 0, n-1, 0);
    long long int highseg = 0;
    if(n%2 == 0){
        highseg = 2*n - 1;
        highseg--;
    }else{
        highseg = 2*pow(2,(n/2)+1) - 1;
        highseg--;
    }
    long long int qlow = 0;
    long long int qhigh = 9;
    for(int i=0; i<4*n+1; i++){
        cout << segTree[i] << " ";
    }
    cout << endl;
    cout << rangeSumQuery(segTree, qlow, qhigh, 0, n-1, 0);
}