fork(3) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int* build(int t[], const int size)
  5. {
  6.     int *segmentTree = new int[2*size];
  7.  
  8.     for(int i = 0; i < size ; i++)
  9.         segmentTree[i+size] = t[i]; /* move original elements to the leaf nodes. */
  10.  
  11.     for(int i = size - 1; i > 0 ; i--) 
  12.     	segmentTree[i] = (segmentTree[i<<1] + segmentTree[i<<1|1]); /* create relation S(i) = S(2i)+ S(2i+1)*/
  13.  
  14.     return segmentTree;
  15. }
  16.  
  17. void modify(int segmentTree[], const int size, int index, int value)
  18. {
  19.     for(segmentTree[index += size] = value; index > 1 ; index>>=1)
  20.     	segmentTree[index>>1] = (segmentTree[index] + segmentTree[index^1]); /* S(i/2) = S(i)+ {S(i+1) or S(i-1)} */
  21. }
  22.  
  23. int query(const int segmentTree[], const int size, int l, int r)
  24. {
  25.     int ans = 0;
  26.     for(l+=size, r+=size; l <= r; l>>=1, r>>=1) {
  27.         if(l&1) ans += segmentTree[l++]; /* if l is left child, parent have the sum. */
  28.         if(r%2 == 0) ans += segmentTree[r--];  /* if r is ritht child, parent have the sum. */
  29.     }
  30.     return ans;
  31. }
  32.  
  33. void printArray(int t[], const int size)
  34. {
  35.     for (int i = 0; i < size; i++)
  36.         cout << t[i] << ", ";
  37.     cout << endl;
  38. }
  39.  
  40. int main()
  41. {
  42.     int t[] = {2, 3, 4, 5, 7, 10, 17};
  43.     int n = sizeof(t)/sizeof(t[0]);
  44.  
  45.     int *segmentTree = build(t, n);
  46.     cout << "segmentTree after build : ";
  47.     printArray(segmentTree, 2*n);
  48.  
  49.      for (int i = 0; i < n; i++)
  50.          for (int j = i; j < n; j++)
  51.             cout <<  "query(" << i << ", " << j << ") : " << query(segmentTree, n, i, j) << endl;
  52.  
  53.     modify(segmentTree, n, 1, 27);
  54.     cout << "array after modify1 : ";
  55.     printArray(segmentTree, 2*n);
  56.  
  57.     modify(segmentTree, n, 5, 77);
  58.     cout << "array after modify2 : ";
  59.     printArray(segmentTree, 2*n);
  60.  
  61.     return 0;
  62. }
Success #stdin #stdout 0s 3272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
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,
https://ideone.com/zWJ0pq
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!