12086 - Potentiometers

/*
+---------------------------------------------+
|                                             |
|       © 26/05/2023 (20:23) MinaMagdy        |
|                                             |
+---------------------------------------------+
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define multi_ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define endl "\n"
#define MOD 1000000007
#define INF 2000000000
#define all(s) s.begin(), s.end()
#define rall(s) s.rbegin(), s.rend()
#define sz(x) int(x.size())

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

vector<ll> seg, arr;
int sz, n;

void build(int N = 1, int l = 0, int r = sz - 1) {
    if (l == r) {
        seg[N] = (l < n ? arr[l] : 0);
        return;
    }
    int m = l + (r - l) / 2;
    build(N * 2, l, m), build(N * 2 + 1, m + 1, r);
    seg[N] = seg[N * 2] + seg[N * 2 + 1];
}

ll query(ll x, ll y, int N = 1, int l = 0, int r = sz - 1) {
    if (y < l || x > r) return 0;
    if (x <= l && r <= y) return seg[N];
    int m = l + (r - l) / 2;
    return query(x, y, N * 2, l, m) + query(x, y, N * 2 + 1, m + 1, r);
}

void update(ll x, ll vl, int N = 1, int l = 0, int r = sz - 1) {
    if (x < l || r < x) return;
    if (l == r) {
        seg[N] = vl;
        return;
    }
    int m = l + (r - l) / 2;
    update(x, vl, N * 2, l, m), update(x, vl, N * 2 + 1, m + 1, r);
    seg[N] = seg[N * 2] + seg[N * 2 + 1];
    return;
}

void solve() {
    int tc = 0;
    while (cin >> n, n) {
        if (tc)
            cout << endl;
        cout << "Case " << ++tc << ":\n";
        arr.assign(n, 0);
        for (int i = 0; i < n; i++) cin >> arr[i];
        sz = 1;
        while (sz < n) sz *= 2;
        seg.assign(sz * 2, 0);
        build();
        char c;
        while (cin >> c, c != 'E') {
            ll x, y;
            cin >> x >> y;
            if (c == 'M') {
                --x, --y;
                cout << query(x, y) << endl;
            }
            else {
                --x;
                update(x, y);
            }
        }
        cin >> c >> c; // for N, D in END
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
    return 0;
}