Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include<algorithm>
- using namespace std;
- 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 mid = (tl + tr) / 2;
- if (pos <= mid) {
- upd(t, 2 * v, tl, mid, pos, x);
- }
- else {
- upd(t, 2 * v + 1, mid + 1, tr + 1, pos, x);
- }
- 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 (l == tl && r == tr) {
- return t[v];
- }
- long long mid = (tl + tr) / 2;
- return sum(t, 2 * v, tl, mid, l, min(r, mid)) + sum(t, 2 * v + 1, mid + 1, tr, max(l, mid + 1), r);
- }
- 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 mid = (tl + tr) / 2;
- build(a, t, 2 * v, tl, mid);
- build(a, t, 2 * v + 1, mid + 1, tr);
- 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 (int i = 0; i < ans.size(); i++) {
- cout << ans[i] << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement