fork download
copy 
  1. // Dynamic (Implicit) Segment tree: We need to create root node and create
  2. // only those child which are required during query and update
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. struct node {
  7.     node *left, *right;
  8.     int sum;
  9.  
  10.     node(): left(NULL), right(NULL), sum(0) {}
  11.  
  12.     void extend() {
  13.         if(!left) { // if left child does not exist, create the children
  14.             left = new node();
  15.             right = new node();
  16.         }
  17.     }
  18.     void update(int index, int updateBy, int l, int r) {
  19.         if(l == r) {
  20.             sum += updateBy; // updateBy = +1/-1vle
  21.             return;
  22.         }
  23.         extend(); // extend before accessing left and right node (extends if child does not exist)
  24.         int mid = (l+r)/2;
  25.         if(index <= mid) {
  26.             left->update(index, updateBy, l, mid);
  27.         } else {
  28.             right->update(index, updateBy, mid+1, r);
  29.         }
  30.         sum = left->sum + right->sum; // update sum of current node
  31.     }
  32.     int getSum(int qs, int qe, int l, int r) {
  33.         // if segment range is outside query range
  34.         if(r < qs || qe < l) {
  35.             return 0;
  36.         }
  37.         // if segment range is contained in query range
  38.         if(qs <=l && r <= qe) {
  39.             return sum;
  40.         }
  41.         extend();
  42.         int mid = (l+r)/2;
  43.         return left->getSum(qs, qe, l, mid) + right->getSum(qs, qe, mid+1, r);
  44.     }
  45. };
  46.  
  47. int main() {
  48.     node* rmq = new node(); // create root node of the tree
  49.     int n, q;
  50.     cin >> n >> q;
  51.     vector<int> a(n);
  52.     for(int i=0;i<n;i++) {
  53.         cin >> a[i];
  54.         rmq->update(a[i], 1, 0, 1e9+1);
  55.     }
  56.     while(q--) {
  57.         char qt;
  58.         cin >> qt;
  59.         if(qt == '?') { //query
  60.             int a, b; cin >> a >> b;
  61.             cout << rmq->getSum(a, b, 0, 1e9+1) << "\n";
  62.         } else { //update
  63.             int k, x; cin >> k >> x;
  64.             rmq->update(a[k-1], -1, 0, 1e9+1); // decrement the sum for existing array value
  65.             rmq->update(x, 1, 0, 1e9+1);      // increment the sum by 1 for new array value array value
  66.             a[k-1] = x;                      // update array with new value
  67.         }
  68.     }
  69. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
10 10
7 9 10 2 8 3 4 7 1 6
? 2 2
? 1 8
? 9 10
? 3 10
? 1 9
? 4 10
? 2 4
? 1 6
? 1 1
? 6 9
stdout
copy 
1
8
2
8
9
7
3
5
1
5
https://ideone.com/QfRtXB
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
secret

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!