bhupixb

Segtree update query build

Aug 9th, 2018
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.16 KB | None | 0 0
  1. /*
  2. I am Hunting High and Low
  3. Diving from the sky above
  4. Looking for, more and more, once again
  5. I'm Hunting High and Low
  6. Sometimes I may win, sometimes I'll lose
  7. It's just a game that I play
  8.  
  9. After the storm there's a calm
  10. Through the clouds shines a ray of the sun
  11. I'm carried from all my harm
  12. There is no one I can't outrun
  13.  
  14. Now I'm leaving my worries behind
  15. Feel the freedom of body and mind
  16. I'm starting my journey, I'm drifting away with the wind, I go___________________:-
  17. */
  18. #include<bits/stdc++.h>
  19. using namespace std;
  20.  
  21. const int N = 1e5 + 50;
  22.  
  23. #define f(i,a,n) for(int i = a; i < n; i++)
  24. #define L cout << '\n';
  25. #define pb(x) push_back(x)
  26. #define C(x) cout << x << ' '
  27. #define A(v) v.begin(), v.end()
  28. #define int long long int
  29. #define ff first
  30. #define ss second
  31.  
  32. int tree[N << 2 + 5], arr[N];
  33. void build(int l, int r, int node){
  34.  
  35. if(l == r){
  36. tree[node] = arr[l];
  37. return;
  38. }
  39.  
  40. int mid = (l + r) / 2;
  41.  
  42. build(l, mid, node * 2);
  43. build(mid + 1, r, (node * 2 )+ 1);
  44.  
  45. tree[node] = tree[node * 2] + tree[node * 2 + 1];
  46. }
  47. int query(int l, int r, int ql, int qr, int node ){
  48. if(r < ql || l > qr)return 0LL;
  49.  
  50. if(ql <= l and r <= qr)
  51. return tree[node];
  52.  
  53. int mid = (l + r) / 2;
  54.  
  55. return query(l, mid, ql, qr, node * 2 + 1) + query(mid + 1, r, ql, qr, node * 2 + 1);
  56. }
  57. void update(int l, int r, int val, int pos, int node){
  58.  
  59. if(l == r and l == pos){
  60. tree[node] = val;
  61. return;
  62. }
  63.  
  64. if(pos < l || pos > r)return;
  65.  
  66. int mid = (l + (r - l) / 2);
  67.  
  68. update(l, mid, val, pos, 2 * node);
  69. update(mid + 1, r, val, pos, 2 * node + 1);
  70. tree[node] = tree[node * 2] + tree[node * 2 + 1];
  71.  
  72. }
  73. signed main(){
  74. ios_base::sync_with_stdio(0);
  75. cin.tie(NULL);cout.tie(NULL);
  76.  
  77. int n, i, l, r, q;
  78. cin >> n;
  79.  
  80. for(i = 1; i <= n; i++){
  81. cin >> arr[i];
  82. }
  83.  
  84. build(1, n, 1);
  85.  
  86. cin >> q;
  87.  
  88. while(q--){
  89. cin >> l >> r;
  90. update(1, n, l, r, 1);
  91. }
  92. C(query(1, n, 1, 3, 1));L;
  93.  
  94. return 0;
  95. }
Add Comment
Please, Sign In to add comment