#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; }
Standard input is empty
segmentTree after build : 0, 48, 19, 29, 7, 12, 27, 2, 3, 4, 5, 7, 10, 17, query(0, 0) : 2 query(0, 1) : 5 query(0, 2) : 9 query(0, 3) : 14 query(0, 4) : 21 query(0, 5) : 31 query(0, 6) : 48 query(1, 1) : 3 query(1, 2) : 7 query(1, 3) : 12 query(1, 4) : 19 query(1, 5) : 29 query(1, 6) : 46 query(2, 2) : 4 query(2, 3) : 9 query(2, 4) : 16 query(2, 5) : 26 query(2, 6) : 43 query(3, 3) : 5 query(3, 4) : 12 query(3, 5) : 22 query(3, 6) : 39 query(4, 4) : 7 query(4, 5) : 17 query(4, 6) : 34 query(5, 5) : 10 query(5, 6) : 27 query(6, 6) : 17 array after modify1 : 0, 72, 43, 29, 31, 12, 27, 2, 27, 4, 5, 7, 10, 17, array after modify2 : 0, 139, 43, 96, 31, 12, 94, 2, 27, 4, 5, 7, 77, 17,