Advertisement
ivnikkk

A

Jun 21st, 2022
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.05 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define debug(l) cerr<<#l<<' '<<l<<'\n';
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. #define all(a) a.begin(), a.end()
  6. typedef long long ll;
  7. typedef pair<ll, ll> pll;
  8. typedef long double ld;
  9. struct Fenwick {
  10.     vector<ll> t;
  11.     Fenwick(ll n) {
  12.         t.resize(n+1);
  13.     }
  14.     ll get(ll i) {
  15.         ll sum = 0;
  16.         for (ll k = i; k > 0; k -= k & -k) {
  17.             sum += t[k];
  18.         }
  19.         return sum;
  20.     }
  21.     ll sum(ll l,ll r) {
  22.         return get(r) - get(l - 1);
  23.     }
  24.     void upd(ll i, ll x) {
  25.         for (ll k = i; k < (ll)t.size(); k += k & -k) {
  26.             t[k] += x;
  27.         }
  28.     }
  29. };
  30. signed main() {
  31. #ifdef _DEBUG
  32.     freopen("input.txt", "r", stdin);
  33.     freopen("output.txt", "w", stdout);
  34. #endif
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(nullptr);
  37.     cout.tie(nullptr);
  38.     ll n, m; cin >> n >> m;
  39.     Fenwick F(n);
  40.     while (m--) {
  41.         char in; cin >> in;
  42.         if (in == 'A') {
  43.             ll ind, x;
  44.             cin >> ind >> x;
  45.             ll last_sum = F.sum(ind, ind);
  46.             x -= last_sum;
  47.             F.upd(ind, x);
  48.         }
  49.         else {
  50.             ll l, r;
  51.             cin >> l >> r;
  52.             cout << F.sum(l, r) << '\n';
  53.         }
  54.     }
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement