#include <algorithm>

/*
 * This code illustrates a segment tree which solves the following problem:
 *
 *     maintain a list of values a0, a1 ... a(n-1) (n fixed) which supports
 *        ai <- x
 *        sum of the elements ai+a(i+1)+...+aj
 *
 * Segment trees can be used to solve a much wider range of problems.
 * For example, it can be adapted to handle the ability to add a constant
 * to all the varaibles in some range.  That is for another set of notes.
 * 
 * First we round up n to N, which is a power of two.  We allocate an
 * array of 2N integers.  This array implicitly represents a tree with
 * the root at position 1, and the leaves are positions N, N+1, N+2,
 * ... 2*N-1.  To move from a node i to its parent we compute
 * floor(i/2).  To move from a node j to its left child we compute
 * 2*j, and to move to its right child we compute 2*j+1.  The
 * following diagram illustrates this for N=4.
 * 
 *                 1
 *                / \
 *               /   \
 *              2     3
 *             / \   / \
 *            4   5 6   7
 *
 * The number shown at a node is the index of that node in the array.
 *
 * So if we're at node j=3 and then 2*j=6, which is the left child
 * and 2*j+1=7 which is the right child.  Similarly if we're at i=6
 * or i=7, then i/2 = 3 which is the parent of i.
 *
 * So to solve the problem at hand, we store the values of the a's in
 * the leaves of the tree.  In each internal node we store the sum of
 * all the a values in the subtree rooted there.
 *
 * For example, suppose that the a values are 2 1 3 2.  Then here is
 * what is stored in the tree (a.k.a. array):
 *
 *                 8
 *                / \
 *               /   \
 *              3     5
 *             / \   / \
 *            2   1 3   2
 *
 * Note that the internal nodes of the tree represent the sum of
 * certain ranges of the array a.  To add a number c to the value of a
 * leaf node, we have to add the same c to all the nodes on the path
 * from that leaf to the root.  The clever function f() below it
 * elegantly computes the sum of any range a[i...j] doing only O(log
 * n) work.
 * 
 *              Danny Sleator <sleator@cs.cmu.edu> 
 *              September, 2015
 */ 

using namespace std; 

#define K 10
#define MAXN (1 << K)

int A[2*MAXN];

int parent (int v) {return v/2;}
int lc (int v) {return 2*v;}
int rc (int v) {return 2*v+1;}

void assign(int v, int x) {
    // We want to assign the value of A[v] to x.
    // This is the same as doing the assignment A[v] += x-A[v]
    // To achieve this we have to add this quantity to
    // every node on the path from v to the root.
    x = x - A[MAXN+v];
    for (int j = MAXN+v; j>0; j = parent(j)) A[j] += x;
}

int f (int v, int l, int r, int ql, int qr) {
    // [l,r] is the range represented by the leaves at
    // the bottom of the subtree rooted at v.
    // [ql,qr] is the query range.  It's always within [l,r]

    int m = (l+r)/2;  // left range is [l,m].  right range is [m+1,r]

    printf("v=%d, l=%d, r=%d, ql=%d, qr=%d\n",v,l,r,ql,qr);

    if (l==ql && r==qr) return A[v];
    int total = 0;
    if (ql <= m) 
        total += f (lc(v), l, m, ql, min(m, qr));
    if (qr > m) 
        total += f (rc(v), m+1, r, max(ql, m+1), qr);
    return total;
}

int sum (int i, int j) {
    return f(1, 0, MAXN-1, i, j);
}

int main() {
    for (int i=0; i<4; i++) {
        assign(i, 2*i);
    }
    
    printf("sum(2,3) = %d\n", sum(2,3));
    printf("sum(0,2) = %d\n", sum(0,2));
    assign(3,239);
    printf("sum(3,3) = %d\n", sum(3,3));    
}