Untitled
unknown
plain_text
a year ago
1.3 kB
8
Indexable
#include <iostream> #include <vector> using namespace std; #define vi vector<int> #define pb push_back #define ll long long #define vl vector<ll> const int S = 320; int n, q; vi a; vl sum; ll stup(int l, int r) { ll res = 0; for (int i = l; i <= r; i++) res += a[i]; return res; } void update(int pos, int val) { sum[pos / S] += val - a[pos]; a[pos] = val; } ll get(int l, int r) { int b1 = l / S; int b2 = r / S; if (b1 == b2) return stup(l, r); ll res = 0; res += stup(l, (b1 + 1) * S - 1); res += (b2 * S, r); for (int b = b1 + 1; b < b2; b++) res += sum[b]; return res; } int main() { freopen("sum.in", "r", stdin); freopen("sum.out", "w", stdout); cin >> n; a.resize(n); for (int i = 0; i < n; i++) cin >> a[i]; cin >> q; sum.resize(n); for (int i = 0; i < n; i++) sum[i] = 0; for (int i = 0; i < n; i++) sum[i / S] += a[i]; while (q--) { int type; cin >> type; if (type == 1) { int pos, x; cin >> pos >> x; pos--; update(pos, x); } else { int l, r; cin >> l >> r; l--; r--; cout << get(l, r) << endl; } } return 0; }
Editor is loading...
Leave a Comment