Advertisement
Guest User

Untitled

a guest
Dec 11th, 2019
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <set>
  4. #include <queue>
  5. #include <vector>
  6. #include <string>
  7. #include <stack>
  8. #include <deque>
  9. #include <cmath>
  10. #include <map>
  11. #include <tuple>
  12.  
  13. using namespace std;
  14.  
  15. int t[5 * 100000];
  16.  
  17. void build(int v, int vl, int vr, int a[]) {
  18.     if (vl == vr) {
  19.         t[v] = a[vl];
  20.         return;
  21.     }
  22.     int vm = vl + (vr - vl) / 2;
  23.     build(2 * v + 1, vl, vm, a);
  24.     build(2 * v + 2, vm + 1, vr, a);
  25.  
  26.     t[v] = t[2 * v + 1] + t[2 * v + 2];
  27. }
  28.  
  29. long long query(int v, int vl, int vr, int l, int r) {
  30.     if (r < vl || vr < l)
  31.         return 0;
  32.     if (l <= vl && vr <= r) return t[v];
  33.     int vm = vl + (vr - vl) / 2;
  34.     long long ql = query(2 * v + 1, vl, vm, l, r);
  35.     long long qr = query(2 * v + 2, vm + 1, vr, l, r);
  36.  
  37.     return ql + qr;
  38. }
  39.  
  40. void change(int v, int vl, int vr, int idx, int val) {
  41.     if (vl == vr) {
  42.         t[v] = val;
  43.         return;
  44.     }
  45.     int vm = vl + (vr - vl) / 2;
  46.     if (idx <= vm)
  47.         change(2 * v + 1, vl, vm, idx, val);
  48.     else
  49.         change(2 * v + 2, vm + 1, vr, idx, val);
  50.  
  51.     t[v] = t[2 * v + 1] + t[2 * v + 2];
  52. }
  53.  
  54. int main() {
  55.     int n, m, a[100000];
  56.     cin >> n;
  57.     for (int i = 0; i < n; i++)
  58.         cin >> a[i];
  59.  
  60.     build(0, 0, n - 1, a);
  61.     cin >> m;
  62.  
  63.     for (int i = 0; i < n; i++) {
  64.         char c;
  65.         int l, r;
  66.         cin >> c >> l >> r;
  67.  
  68.         if (c == 's') {
  69.             cout << query(0, 0, n - 1, l - 1, r - 1) << " ";
  70.         } else {
  71.             change(0, 0, n - 1, l - 1, r);
  72.         }
  73.     }
  74.     return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement