fork download
copy 
  1. // C++ code for segment tree with sum
  2. // range and update query
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. vector<int> A, ST;
  7.  
  8. void build(int node, int L, int R)
  9. {
  10.  
  11.     // Leaf node where L == R
  12.     if (L == R) {
  13.     	cout<<"["<<L<<","<<R<<","<<node<<"]\n";
  14.         ST[node] = A[L];
  15.     }
  16.     else {
  17.  
  18.         // Find the middle element to
  19.         // split the array into two halves
  20.         int mid = (L + R) / 2;
  21.  
  22.         // Recursively travel the
  23.         // left half
  24.         build(2 * node, L, mid);
  25.  
  26.         // Recursively travel the
  27.         // right half
  28.         build(2 * node + 1, mid + 1, R);
  29.  
  30. 		cout<<"["<<L<<","<<R<<","<<node<<"]\n";
  31.         // Storing the sum of both the
  32.         // children into the parent
  33.         ST[node] = ST[2 * node] + ST[2 * node + 1];
  34.     }
  35. }
  36.  
  37. void update(int node, int L, int R, int idx, int val)
  38. {
  39.  
  40.     // Find the lead node and
  41.     // update its value
  42.     if (L == R) {
  43.         A[idx] += val;
  44.         ST[node] += val;
  45.     }
  46.     else {
  47.  
  48.         // Find the mid
  49.         int mid = (L + R) / 2;
  50.  
  51.         // If node value idx is at the
  52.         // left part then update
  53.         // the left part
  54.         if (L <= idx and idx <= mid)
  55.             update(2 * node, L, mid, idx, val);
  56.         else
  57.             update(2 * node + 1, mid + 1, R, idx, val);
  58.  
  59.         // Store the information in parents
  60.         ST[node] = ST[2 * node] + ST[2 * node + 1];
  61.     }
  62. }
  63.  
  64. int query(int node, int tl, int tr, int l, int r)
  65. {
  66.  
  67.     // If it lies out of range then
  68.     // return 0
  69.     if (r < tl or tr < l)
  70.         return 0;
  71.  
  72.     // If the node contains the range then
  73.     // return the node value
  74.     if (l <= tl and tr <= r)
  75.         return ST[node];
  76.     int tm = (tl + tr) / 2;
  77.  
  78.     // Recursively traverse left and right
  79.     // and find the node
  80.     return query(2 * node, tl, tm, l, r)
  81.            + query(2 * node + 1, tm + 1, tr, l, r);
  82. }
  83.  
  84. // Driver code
  85. int main()
  86. {
  87.     int n = 6;
  88.     A = { 0, 1, 3, 5, -2, 3 };
  89.  
  90.     // Create a segment tree of size 4*n
  91.     ST.resize(4 * n);
  92.  
  93.     // Build a segment tree
  94.     build(1, 0, n - 1);
  95.     cout << "Sum of values in range 0-4 are: "
  96.          << query(1, 0, n - 1, 0, 4) << "\n";
  97.  
  98.     // Update the value at idx = 1 by
  99.     // 100 thus becoming 101
  100.     update(1, 0, n - 1, 1, 100);
  101.     cout << "Value at index 1 increased by 100\n";
  102.     cout << "sum of value in range 1-3 are: "
  103.          << query(1, 0, n - 1, 1, 3) << "\n";
  104.  
  105.     return 0;
  106. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[0,0,8]
[1,1,9]
[0,1,4]
[2,2,5]
[0,2,2]
[3,3,12]
[4,4,13]
[3,4,6]
[5,5,7]
[3,5,3]
[0,5,1]
Sum of values in range 0-4 are: 7
Value at index 1 increased by 100
sum of value in range 1-3 are: 109
https://ideone.com/S79xS3
language:
C++14 (gcc 8.3)
created:
8 days 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!