#include <iostream>
#include "data.h" //arr, N

using namespace std;

#define ROOT 1
#define father(x) (x/2)
#define left(x)   (2*x)
#define right(x)  (2*x+1)

#define mid(l, r) (l+(r-l)/2)

int st[2*N+2]; //segment tree sits in flat in memory
int map[N];

//binary operation
int f(int a, int b) {
    return a + b; //could be min(a,b);
                  // arr[a] < arr[b] ? a : b;
}

void construct(int cur, int a, int b) {
    if (a == b) {
        map[a] = cur;
        st[cur] = arr[a];
    
        return;
    }
    
    construct(left(cur),  a, mid(a, b));
    construct(right(cur),  mid(a, b)+1, b);
    
    st[cur] = f(st[left(cur)], st[right(cur)]);
}


void update(int index, int val) {
    int cur = father(map[index]);
    
    st[map[index]] = val;
    
    while (cur != ROOT) {
       st[cur] = f(st[left(cur)], st[right(cur)]);
        cur = father(cur);
    }
     st[cur] = f(st[left(cur)], st[right(cur)]);
}

int get(int cur, int a, int b, int i, int j) {
    if (j < a)
        return 0;
    if (i > b)
        return 0;
    if (a <= i && j <= b)
        return st[cur];
    
    return f(get(left(cur),   a, b, i, mid(i, j)),
             get(right(cur),  a, b, mid(i, j)+1, j));
}

int get(int a, int b) {
    return get(ROOT, a, b, 0, N-1);
}

int main()
{
   printArr();
   construct(ROOT, 0, N-1);  
   cout <<  "RSQ(0, N-1) = " << get (0, N-1) <<endl;
   cout <<  "RSQ(7, 9)   = " << get (7, 9) <<endl;
}
