根本不需要什么树状数组。

考虑数组和差分两种做法。一种是 $O(n)$ 区间修 $O(1)$ 单点求值。一种是 $O(1)$ 区间修 $O(n)$ 求值。

我们可以给出第一个优化：如果询问 $\le \dfrac{q}{2}$ 次用第一种方法。否则用第二种方法。

这样可以做到不超过 $\dfrac{nq}{2}$。实测跑了 $762 \text{ms}$。

还能优化吗？当然可以啦。如果是 $5 \times 10^9$ 次的运算，就不会有这篇题解了。

算法一可以优化常数。如果区间长度 $\leq \dfrac{n}{2}$，可以直接加。否则可以全局打个标记，对区间外的减。

算法二也可以优化常数。如果查询的点在前一半，可以直接加差分，否则维护最后一个数的值，从后往前减。

那么这样就等价于 $n$ 和 $q$ 都变成了 $5 \times 10^4$。而时限竟然有足足 $2\text{s}$！这意味着极限数据下 $O(nq)$ 也可以轻松在 QOJ 上通过。实测跑到了 $367\text{ms}$。

至此，不会树状数组的我们解决了这个题。

#include<bits/stdc++.h>
using namespace std;
int n, m, cnt;
long long a[100005], cf[100005], tag, sum;
struct que{
    int op, l, r, k, pos;
}Q[100005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; i++){
        cin >> Q[i].op;
        if (Q[i].op == 1)
            cin >> Q[i].l >> Q[i].r >> Q[i].k;
        else{
            cin >> Q[i].pos;
            cnt++;
        }
    }
    if (cnt <= (n / 2)){
        for (int i = 1; i <= n; i++)
            cf[i] = a[i] - a[i - 1];
        sum = a[n];
        for (int _ = 1; _ <= m; _++){
            int op = Q[_].op;
            if (op == 1){
                int l = Q[_].l, r = Q[_].r, k = Q[_].k;
                cf[l] += k;
                cf[r + 1] -= k;
                if (r >= n)
                    sum += k;
            }else{
                int pos = Q[_].pos;
                long long ans = 0;
                if (pos <= n / 2){
                    for (int i = 1; i <= pos; i++)
                        ans += cf[i];
                }else{
                    ans = sum;
                    for (int i = n; i > pos; i--)
                        ans -= cf[i];
                }
                cout << ans << "\n";
            }
        }
    }else{
        for (int _ = 1; _ <= m; _++){
            int op = Q[_].op;
            if (op == 1){
                int l = Q[_].l, r = Q[_].r, k = Q[_].k;
                if (r - l <= (n / 2)){
                    for (int i = l; i <= r; i++)
                        a[i] += k;
                }else{
                    tag += k;
                    for (int i = 1; i < l; i++)
                        a[i] -= k;
                    for (int i = n; i > r; i--)
                        a[i] -= k;    
                }
            }else if (op == 2){
                int pos = Q[_].pos;
                cout << a[pos] + tag << "\n";
            }
        }
    }
    return 0;
}