fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. class SegmentTree {
  6. public:
  7.     vector<int> tree;
  8.     int n;
  9.  
  10.     SegmentTree(int size) {
  11.         n = size;
  12.         tree.resize(4 * n, 0);  // Initialize the segment tree with 0
  13.     }
  14.  
  15.     // Build the segment tree from the array
  16.     void build(const vector<int>& arr, int node, int start, int end) {
  17.         if (start == end) {
  18.             tree[node] = arr[start];  // Leaf node stores array value
  19.         } else {
  20.             int mid = (start + end) / 2;
  21.             build(arr, 2 * node + 1, start, mid);  // Build left subtree
  22.             build(arr, 2 * node + 2, mid + 1, end);  // Build right subtree
  23.             tree[node] = tree[2 * node + 1] + tree[2 * node + 2];  // Internal node
  24.         }
  25.     }
  26.  
  27.     // Query the sum of elements in range [L, R]
  28.     int query(int node, int start, int end, int L, int R) {
  29.         if (R < start || end < L) {
  30.             return 0;  // No overlap
  31.         }
  32.         if (L <= start && end <= R) {
  33.             return tree[node];  // Total overlap
  34.         }
  35.         int mid = (start + end) / 2;
  36.         int left_query = query(2 * node + 1, start, mid, L, R);  // Query left subtree
  37.         int right_query = query(2 * node + 2, mid + 1, end, L, R);  // Query right subtree
  38.         return left_query + right_query;  // Combine the results
  39.     }
  40.  
  41.     // Update the value at a specific index
  42.     void update(int node, int start, int end, int idx, int value) {
  43.         if (start == end) {
  44.             tree[node] = value;  // Update leaf node
  45.         } else {
  46.             int mid = (start + end) / 2;
  47.             if (start <= idx && idx <= mid) {
  48.                 update(2 * node + 1, start, mid, idx, value);  // Update left subtree
  49.             } else {
  50.                 update(2 * node + 2, mid + 1, end, idx, value);  // Update right subtree
  51.             }
  52.             tree[node] = tree[2 * node + 1] + tree[2 * node + 2];  // Update internal node
  53.         }
  54.     }
  55. };
  56.  
  57. int main() {
  58.     int n;
  59.     cin >> n;  // Input the size of the array
  60.     vector<int> arr(n);
  61.  
  62.     // Input the array elements
  63.     for (int i = 0; i < n; i++) {
  64.         cin >> arr[i];
  65.     }
  66.  
  67.     SegmentTree segment_tree(n);
  68.     segment_tree.build(arr, 0, 0, n - 1);  // Build the segment tree
  69.  
  70.     int L, R;
  71.     cin >> L >> R;  // Input the range for the query
  72.     cout << segment_tree.query(0, 0, n - 1, L, R) << endl;  // Output the sum in the range
  73.  
  74.     int idx, value;
  75.     cin >> idx >> value;  // Input the index and new value for update
  76.     segment_tree.update(0, 0, n - 1, idx, value);  // Update the segment tree
  77.  
  78.     cin >> L >> R;  // Input the new range for the query
  79.     cout << segment_tree.query(0, 0, n - 1, L, R) << endl;  // Output the updated sum in the range
  80.  
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
6
1 3 5 7 9 11
1 3
1 10
1 3
stdout
copy 
15
22
https://ideone.com/O4WHPd
Range Sum Query
1, Build a Segment Tree for an array of integers.
2, Query the sum of elements in a given range [L, R].
3, Update the value of an element in the array and update the tree accordingly.
language:
C++ (gcc 8.3)
created:
1 day 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!