Advertisement
Josif_tepe

Untitled

Feb 12th, 2023
941
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <set>
  5. #include <cmath>
  6. #include <map>
  7. using namespace std;
  8. const int maxn = 2e5 + 10;
  9. typedef long long ll;
  10. int a[maxn];
  11. ll segment_tree[3 * maxn];
  12.  
  13. void build_tree(int L, int R, int position) {
  14.     if(L == R) {
  15.         segment_tree[position] = a[L];
  16.     }
  17.     else {
  18.         int mid = (L + R) / 2;
  19.         build_tree(L, mid, 2 * position);
  20.         build_tree(mid + 1, R, 2 * position + 1);
  21.        
  22.         segment_tree[position] = segment_tree[2 * position] + segment_tree[2 * position + 1];
  23.     }
  24.    
  25. }
  26. // L R i L R j L R
  27. ll query(int L, int R, int position, int i, int j) {
  28.     if(R < i or j < L) {
  29.         return 0;
  30.     }
  31.     if(i <= L and R <= j) {
  32.         return segment_tree[position];
  33.     }
  34.     int mid = (L + R) / 2;
  35.     return query(L, mid, 2 * position, i, j) + query(mid + 1, R, 2 * position + 1, i, j);
  36. }
  37. void update(int L, int R, int position, int idx, int new_value) {
  38.     if(L == R) {
  39.         segment_tree[position] = new_value;
  40.         return;
  41.     }
  42.     int mid = (L + R) / 2;
  43.     if(idx <= mid) {
  44.         update(L, mid, 2 * position, idx, new_value);
  45.     }
  46.     else {
  47.         update(mid + 1, R, 2 * position + 1, idx, new_value);
  48.     }
  49.     segment_tree[position] = segment_tree[2 * position] + segment_tree[2 * position + 1];
  50. }
  51. int main() {
  52.     ios_base::sync_with_stdio(false);
  53.     int n, q;
  54.     cin >> n >> q;
  55.    
  56.     for(int i = 0; i < n; i++) {
  57.         cin >> a[i];
  58.     }
  59.    
  60.     build_tree(0, n - 1, 1); // build the segment tree
  61.    
  62.     for(int i = 0; i < q; i++) {
  63.         int type;
  64.         cin >> type;
  65.        
  66.         if(type == 1) {
  67.             int u, k;
  68.             cin >> u >> k;
  69.             u--;
  70.             update(0, n - 1, 1, u, k);
  71.         }
  72.         else {
  73.             int x, y;
  74.             cin >> x >> y;
  75.             x--;
  76.             y--;
  77.             cout << query(0, n - 1, 1, x, y) << endl;
  78.         }
  79.     }
  80.    
  81.    
  82.     return 0;
  83. }
  84.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement