#include <iostream>
using namespace std;

int* build(int t[], const int size)
{
    int *segmentTree = new int[2*size];
	
    for(int i = 0; i < size ; i++)
        segmentTree[i+size] = t[i]; /* move original elements to the leaf nodes. */
		
    for(int i = size - 1; i > 0 ; i--) 
    	segmentTree[i] = (segmentTree[i<<1] + segmentTree[i<<1|1]); /* create relation S(i) = S(2i)+ S(2i+1)*/
    	
    return segmentTree;
}
 
void modify(int segmentTree[], const int size, int index, int value)
{
    for(segmentTree[index += size] = value; index > 1 ; index>>=1)
    	segmentTree[index>>1] = (segmentTree[index] + segmentTree[index^1]); /* S(i/2) = S(i)+ {S(i+1) or S(i-1)} */
}
 
int query(const int segmentTree[], const int size, int l, int r)
{
    int ans = 0;
    for(l+=size, r+=size; l <= r; l>>=1, r>>=1) {
        if(l&1) ans += segmentTree[l++]; /* if l is left child, parent have the sum. */
        if(r%2 == 0) ans += segmentTree[r--];  /* if r is ritht child, parent have the sum. */
    }
    return ans;
}

void printArray(int t[], const int size)
{
    for (int i = 0; i < size; i++)
        cout << t[i] << ", ";
    cout << endl;
}

int main()
{
    int t[] = {2, 3, 4, 5, 7, 10, 17};
    int n = sizeof(t)/sizeof(t[0]);

    int *segmentTree = build(t, n);
    cout << "segmentTree after build : ";
    printArray(segmentTree, 2*n);
	
     for (int i = 0; i < n; i++)
         for (int j = i; j < n; j++)
            cout <<  "query(" << i << ", " << j << ") : " << query(segmentTree, n, i, j) << endl;
    
    modify(segmentTree, n, 1, 27);
    cout << "array after modify1 : ";
    printArray(segmentTree, 2*n);
    
    modify(segmentTree, n, 5, 77);
    cout << "array after modify2 : ";
    printArray(segmentTree, 2*n);
	
    return 0;
}