Простой splay на сумму и изменение в точке

#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple

const int N = 1e6;

struct node {
    int s[2];
    int p;
    int f;
    int v;
} pool[N];

#define son(x, i) pool[x].s[i]
#define ls(x) pool[x].s[0]
#define rs(x) pool[x].s[1]
#define pr(x) pool[x].p
#define fn(x) pool[x].f
#define va(x) pool[x].v

int who(int v) {
    if (v == ls(pr(v))) {
        return 0;
    } else {
        assert(v == rs(pr(v)));
        return 1;
    }
}

int pull(int v) {
    fn(v) = fn(ls(v)) + va(v) + fn(rs(v));
    return v;
}

void rot(int v) {
    int p = pr(v);
    // assert(p);
    int g = pr(p);
    int w = who(v);

    if (g) {
        son(g, who(p)) = v;
        pr(v) = g;
        pull(g);
    } else {
        pr(v) = 0;
    }

    int &u = son(v, w ^ 1);

    son(p, w) = u;
    pr(u) = p;
    pull(p);

    u = p;
    pr(p) = v;
    pull(v);
}

void splay(int v) {
    while (pr(v)) {
        int p = pr(v), g = pr(p);
        if (!g) {
            rot(v);
        } else if (who(v) == who(p)) {
            rot(p);
            rot(v);
        } else {
            rot(v);
            rot(v);
        }
    }
}

void print(int v, int h = 0) {
    if (v) {
        print(ls(v), h + 1);
        cout << string(4 * h, ' ') << " " << v << endl;
        print(rs(v), h + 1);
    }
    if (!h) {
        cout << "======" << endl;
    }
}

int n, m;
int t = 0;

int prefix(int v) {
    if (!v) {
        return 0;
    }
    splay(t = v);
    return fn(ls(v)) + va(v);
}

int query(int l, int r) {
    return prefix(r) - prefix(l - 1);
}

void update(int x, int y) {
    va(x) = y;
    pull(x);
    splay(t = x);
}

signed main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(0); cin.tie(0);

    mt19937 rnd;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> va(i);
        ls(i) = t;
        pr(t) = i;
        t = i;
        pull(t);
    }

    char tp;
    int hhh = 0;
    for (int x, y, i = 0; i < m; ++i) {
        cin >> tp >> x >> y;
        if (tp == '?') {
            int cur = query(x, y);
            hhh += cur;
        } else {
            update(x, y);
        }
    }

    cout << "#" << hhh << endl;
    cout << 1000 * clock() / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}