zhukov000

SegTree

Sep 25th, 2021
1,109
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <iterator>
  4.  
  5. using LL = long long;
  6.  
  7. struct SegmentTree {
  8.     std::vector<LL> tree;
  9.     int size;
  10.  
  11.     LL combine(const LL & left, const LL & right) {
  12.         return {left + right};
  13.     }
  14.  
  15.     void build(const std::vector<int> & data, int x, int l, int r) {
  16.         if (r - l == 1) {
  17.             if (l < data.size()) {
  18.                 tree[x] = data[l];
  19.             } else {
  20.                 tree[x] = 0; // нейтральное значение
  21.             }
  22.             return;
  23.         }
  24.         int m = (l + r) / 2;
  25.         build(data, 2*x+1, l, m);
  26.         build(data, 2*x+2, m, r);
  27.         tree[x] = combine(tree[2*x+1], tree[2*x+2]);
  28.     }
  29.  
  30.     void build(const std::vector<int> & data) {
  31.         size = 1;
  32.         while (size <= data.size()) {
  33.             size *= 2;
  34.         }
  35.         tree.resize(2 * size);
  36.         build(data, 0, 0, size);
  37.     }
  38.  
  39.     void set_up(int i, int v) {
  40.         i += size - 1;
  41.         tree[i] = v;
  42.         while (i > 0) {
  43.             i = (i - 1) / 2;
  44.             tree[i] = combine(tree[2*i+1], tree[2*i+2]);
  45.         }
  46.     }
  47.  
  48.     LL sum_up(int l, int r) {
  49.         LL ans = 0;
  50.         l += size - 1;
  51.         r += size - 2;
  52.         while (l <= r) {
  53.             if (l % 2 == 0) {
  54.                 ans += tree[l];
  55.             }
  56.             if (r % 2 != 0) {
  57.                 ans += tree[r];
  58.             }
  59.             l = l / 2;
  60.             r = r / 2 - 1;
  61.         }
  62.         return ans;
  63.     }
  64.  
  65.     void set(int i, int v, int x, int lx, int rx) {
  66.         if (rx - lx == 1) {
  67.             tree[x] = v;
  68.             return;
  69.         }
  70.         int mx = (lx + rx) / 2;
  71.         if (i < mx) {
  72.             set(i, v, 2*x+1, lx, mx);
  73.         } else {
  74.             set(i, v, 2*x+2, mx, rx);
  75.         }
  76.         tree[x] = combine(tree[2*x+1], tree[2*x+2]);
  77.     }
  78.  
  79.     void set(int i, int v) {
  80.         set(i, v, 0, 0, size);
  81.     }
  82.  
  83.     LL sum(int l, int r, int x, int lx, int rx) {
  84.         if (l >= rx || r <= lx) {
  85.             return 0;
  86.         }
  87.         if (l <= lx && rx <= r) {
  88.             return tree[x];
  89.         }
  90.         int mx = (lx + rx) / 2;
  91.         LL ls = sum(l, r, 2*x+1, lx, mx);
  92.         LL rs = sum(l, r, 2*x+2, mx, rx);
  93.         return combine(ls, rs);
  94.     }
  95.  
  96.     LL sum(int l, int r) {
  97.         return sum(l, r, 0, 0, size);
  98.     }
  99.  
  100.     void print() {
  101.         for(int i=0; i<tree.size(); ++i){
  102.             std::cout << tree[i] << ' ';
  103.         }
  104.         std::cout << '\n';
  105.     }
  106. };
  107.  
  108. int main() {
  109.     std::ios_base::sync_with_stdio(0);
  110.     std::cin.tie(0);
  111.     std::cout.tie(0);
  112.  
  113.     int n, m;
  114.     std::cin >> n >> m;
  115.     std::vector<int> data;
  116.     for(int i = 0; i<n; ++i) {
  117.         int x;
  118.         std::cin >> x;
  119.         data.push_back({x});
  120.     }
  121.  
  122.     SegmentTree st;
  123.     st.build(data);
  124.     // st.print();
  125.  
  126.     for(int j=0; j<m; ++j) {
  127.         int t;
  128.         std::cin >> t;
  129.         if (t == 1) {
  130.             int i, v;
  131.             std::cin >> i >> v;
  132.             st.set_up(i, v); // снизу вверх
  133.             // st.set(i, v);
  134.         } else {
  135.             int l, r;
  136.             std::cin >> l >> r;
  137.             std::cout << st.sum_up(l, r) << '\n';  // снизу вверх
  138.             // std::cout << st.sum(l, r) << '\n';
  139.         }
  140.     }
  141.  
  142.     return 0;
  143. }
  144.  
RAW Paste Data