Advertisement
apachee

Untitled

Jul 3rd, 2022
1,319
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.02 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. struct segtree {
  7.     vector<ll>tree;
  8.     int size;
  9.  
  10.     void init(int n) {
  11.         size = 1;
  12.         while(size < n) size *= 2;
  13.         tree.assign(2 * size - 1, 0);
  14.     }
  15.  
  16.     void build(vector<int> &a, int x, int lx, int rx) {
  17.         if(rx - lx == 1) {
  18.             if(lx < a.size()) {
  19.                 tree[x] = a[lx];
  20.             }
  21.         }
  22.         else {
  23.             int m = (lx + rx) / 2;
  24.             build(a, 2 * x + 1, lx, m);
  25.             build(a, 2 * x + 2, m, rx);
  26.             tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
  27.         }
  28.     }
  29.  
  30.     void build(vector<int> &a) {
  31.         init(a.size());
  32.         build(a, 0, 0, size);
  33.     }
  34.  
  35.     void set(int i, int v, int x, int lx, int rx) {
  36.         if(rx - lx == 1) {
  37.             tree[x] += v;
  38.             return;
  39.         }
  40.         int m = (lx + rx) / 2;
  41.         if(i < m) {
  42.             set(i, v, 2 * x + 1, lx, m);
  43.         }
  44.         else {
  45.             set(i, v, 2 * x + 2, m, rx);
  46.         }
  47.         tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
  48.     }
  49.     void set(int i, int v) {
  50.         set(i, v, 0, 0, size);
  51.     }
  52.     long long sum(int l, int r, int x, int lx, int rx) {
  53.         if(l >= rx || lx >= r) {
  54.             return 0;
  55.         }
  56.         if(lx >= l && rx <= r) {
  57.             return tree[x];
  58.         }
  59.         int m = (lx + rx) / 2;
  60.         long long s1 = sum(l, r, 2 * x + 1, lx, m);
  61.         long long s2 = sum(l, r, 2 * x + 2, m, rx);
  62.         return s1 + s2;
  63.     }
  64.     long long sum(int l, int r) {
  65.         return sum(l, r, 0, 0, size);
  66.     }
  67. };
  68.  
  69. int main() {
  70.     int n, m;
  71.     cin >> n >> m;
  72.     segtree st;
  73.     vector<int>a(n, 0);
  74.     st.build(a);
  75.     for(int t = 0; t < m; t++) {
  76.         int c;
  77.         cin >> c;
  78.         if(c == 2) {
  79.             int i, v;
  80.             cin >> i >> v;
  81.             st.set(i, v);
  82.         }
  83.         else {
  84.             int l, r;
  85.             cin >> l >> r;
  86.             cout << st.sum(l - 1, r - 1) << endl;
  87.         }
  88.     }
Advertisement
RAW Paste Data Copied
Advertisement