Advertisement
Ginger_samurai

Untitled

Feb 3rd, 2020
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.88 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. using namespace std;
  5.  
  6.  
  7. void upd(vector<long long>& t, long long v, long long tl, long long tr, long long pos, long long x) {
  8.     if (tl == tr) {
  9.         t[v] = x;
  10.         return;
  11.     }
  12.     long long mid = (tl + tr) / 2;
  13.     if (pos <= mid) {
  14.         upd(t, 2 * v, tl, mid, pos, x);
  15.     }
  16.     else {
  17.         upd(t, 2 * v + 1, mid + 1, tr + 1, pos, x);
  18.     }
  19.     t[v] = t[2 * v] + t[2 * v + 1];
  20.     return;
  21. }
  22.  
  23.  
  24.  
  25. long long sum(vector<long long>& t, long long v, long long tl, long long tr, long long l, long long r) {
  26.     if (l > r) {
  27.         return 0;
  28.     }
  29.     if (l == tl && r == tr) {
  30.         return t[v];
  31.     }
  32.     long long mid = (tl + tr) / 2;
  33.     return sum(t, 2 * v, tl, mid, l, min(r, mid)) + sum(t, 2 * v + 1, mid + 1, tr, max(l, mid + 1), r);
  34. }
  35.  
  36.  
  37.  
  38.  
  39.  
  40.  
  41. void build(vector<long long>& a, vector<long long>& t, long long v, long long tl, long long tr) {
  42.     if (tl == tr) {
  43.         t[v] = a[tl];
  44.         return;
  45.     }
  46.  
  47.     long long mid = (tl + tr) / 2;
  48.     build(a, t, 2 * v, tl, mid);
  49.     build(a, t, 2 * v + 1, mid + 1, tr);
  50.     t[v] = t[2 * v] + t[2 * v + 1];
  51.     return;
  52. }
  53.  
  54.  
  55.  
  56.  
  57.  
  58.  
  59. int main() {
  60.     long long n;
  61.     cin >> n;
  62.     vector<long long> a(n), t(4 * n), ans;
  63.  
  64.     for (long long i = 0; i < n; i++) {
  65.         cin >> a[i];
  66.     }
  67.     build(a, t, 1, 0, n - 1);
  68.     long long k;
  69.     cin >> k;
  70.     for (long long i = 0; i < k; i++) {
  71.         char c;
  72.         cin >> c;
  73.         if (c == 's') {
  74.             long long f, g;
  75.             cin >> f >> g;
  76.             ans.push_back( sum(t, 1, 0, n - 1, f - 1, g - 1) );
  77.         }
  78.         else {
  79.             long long f, g;
  80.             cin >> f >> g;
  81.             upd(t, 1, 0, n - 1, f - 1, g);
  82.         }
  83.     }
  84.  
  85.     for (int i = 0; i < ans.size(); i++) {
  86.         cout << ans[i] << " ";
  87.     }
  88.  
  89.  
  90.  
  91.     return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement