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