Advertisement
Ginger_samurai

Untitled

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