Advertisement
cosenza987

Untitled

Aug 4th, 2021
860
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.48 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define int long long
  4.  
  5. using namespace std;
  6.  
  7. const int maxn = 1e5 + 7;
  8.  
  9. int st[4 * maxn], v[maxn];
  10.  
  11. void build(int p, int l, int r) {
  12.     if(l == r) {
  13.         st[p] = v[l];
  14.         return;
  15.     }
  16.     build(2 * p, l, (l + r) / 2);
  17.     build(2 * p + 1, (l + r) / 2 + 1, r);
  18.     st[p] = st[2 * p] + st[2 * p + 1];
  19. }
  20.  
  21. int query(int p, int l, int r, int i, int j) {
  22.     if(r < i or j < l) {
  23.         return 0;
  24.     }
  25.     if(i <= l and r <= j) {
  26.         return st[p];
  27.     }
  28.     int x = query(2 * p, l, (l + r) / 2, i, j);
  29.     int y = query(2 * p + 1, (l + r) / 2 + 1, r, i, j);
  30.     return x + y;
  31. }
  32.  
  33. void update(int p, int l, int r, int x, int v) {
  34.     if(x < l or r < x) {
  35.         return;
  36.     }
  37.     if(l == r and l == x) {
  38.         st[p] += v;
  39.         return;
  40.     }
  41.     update(2 * p, l, (l + r) / 2, x, v);
  42.     update(2 * p + 1, (l + r) / 2 + 1, r, x, v);
  43.     st[p] = st[2 * p] + st[2 * p + 1];
  44. }
  45.  
  46. main() {
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(0);
  49.     int n;
  50.     cin >> n;
  51.     for(int i = 0; i < n; i++) {
  52.         cin >> v[i];
  53.     }
  54.     build(1, 0, n - 1);
  55.     int q;
  56.     cin >> q;
  57.     while(q--) {
  58.         char qq;
  59.         cin >> qq;
  60.         if(qq == 'q') {
  61.             int l, r;
  62.             cin >> l >> r;
  63.             cout << query(1, 0, n - 1, l - 1, r - 1) << "\n";
  64.         } else {
  65.             int x, v;
  66.             cin >> x >> v;
  67.             update(1, 0, n - 1, x - 1, v);
  68.         }
  69.     }
  70.     return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement