fork download
  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
stdin
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
1
8
2
8
9
7
3
5
1
5