#include
/*
* 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
* 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));
}