Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define int int64_t
- using namespace std;
- struct vertex {
- int sum = 0;
- };
- ostream& operator << (ostream& out, const vertex& v) {
- return out << v.sum;
- }
- const int N = 1e5 + 1;
- array<int, N> a;
- array<vertex, 4 * N> t;
- vertex merge(vertex l, vertex r) {
- vertex cur{};
- cur.sum = l.sum + r.sum;
- return cur;
- }
- void build(int v, int tl, int tr) {
- if (tr - tl == 1) {
- t[v].sum = a[tl];
- return;
- }
- int tm = (tl + tr) / 2;
- build(v * 2, tl, tm);
- build(v * 2 + 1, tm, tr);
- t[v] = merge(t[v * 2], t[v * 2 + 1]);
- }
- void update(int v, int tl, int tr, int i, int x) {
- if (tr - tl == 1) {
- t[v].sum = x;
- return;
- }
- int tm = (tl + tr) / 2;
- if (i < tm) {
- update(v * 2, tl, tm, i, x);
- } else {
- update(v * 2 + 1, tm, tr, i, x);
- }
- t[v] = merge(t[v * 2], t[v * 2 + 1]);
- }
- vertex get(int v, int tl, int tr, int l, int r) {
- if (r <= tl || l >= tr) {
- return vertex(0);
- }
- if (l <= tl && r >= tr) {
- return t[v];
- }
- int tm = (tl + tr) / 2;
- return merge(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm, tr, l, r));
- }
- int32_t main() {
- int n;
- cin >> n;
- for (int i = 0; i < n; i++) {
- cin >> a[i];
- }
- build(1, 0, n);
- int q;
- cin >> q;
- while (q--) {
- char c;
- cin >> c;
- if (c == 'u') {
- int i, x;
- cin >> i >> x;
- i--;
- update(1, 0, n, i, x);
- } else {
- int l, r;
- cin >> l >> r;
- l--;
- cout << get(1, 0, n, l, r) << ' ';
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment