Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include<algorithm>
- using namespace std;
- void build(vector<long long>& a, vector<long long>& t, long long v, long long tl, long long tr) {
- if (tl == tr) {
- t[v] = a[tl];
- return;
- }
- long long tm = (tl + tr) / 2;
- build(a, t, 2 * v, tl, tm);
- build(a, t, 2 * v + 1, tm + 1, tr);
- t[v] = t[2 * v] + t[2 * v + 1];
- return;
- }
- long long sum(vector<long long>& t, long long v, long long tl, long long tr, long long l, long long r) {
- if (l > r) {
- return 0;
- }
- if (tl == l && tr == r) {
- return t[v];
- }
- long long tm = (tl + tr) / 2;
- return sum(t, 2 * v, tl, tm, l, min(r, tm)) + sum(t, 2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
- }
- void upd(vector<long long>& t, long long v, long long tl, long long tr, long long pos, long long x) {
- if (tl == tr) {
- t[v] = x;
- return;
- }
- long long tm = (tl + tr) / 2;
- if (pos <= tm) {
- upd(t, 2 * v, tl, tm, pos, x);
- }
- else {
- upd(t, 2 * v + 1, tm + 1, tr, pos, x);
- }
- t[v] = t[2 * v] + t[2 * v + 1];
- return;
- }
- int main() {
- long long n;
- cin >> n;
- vector<long long>a(n), t(4*n), ans;
- for (long long i = 0; i < n; i++) {
- cin >> a[i];
- }
- build(a, t, 1, 0, n - 1);
- long long k;
- cin >> k;
- for (long long i = 0; i < k; i++) {
- char c;
- cin >> c;
- if (c == 's') {
- long long f, g;
- cin >> f >> g;
- ans.push_back(sum(t, 1, 0, n - 1, f - 1, g - 1));
- }
- else {
- long long f, g;
- cin >> f >> g;
- upd(t, 1, 0, n - 1, f - 1, g);
- }
- }
- for (long long i = 0; i < ans.size(); i++) {
- cout << ans[i] << " ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement