Hint
A segment tree for the maximum. Building up is an update of one element: the new height is the old one plus h, so keep the array of heights as well.
Solution (C++)
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int n;
vector<long long> a, t;
void build(int v, int l, int r) {
if (l == r) { t[v] = a[l]; return; }
int m = (l + r) / 2;
build(2 * v, l, m);
build(2 * v + 1, m + 1, r);
t[v] = max(t[2 * v], t[2 * v + 1]);
}
long long query(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return LLONG_MIN;
if (ql <= l && r <= qr) return t[v];
int m = (l + r) / 2;
return max(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}
void update(int v, int l, int r, int i, long long x) {
if (l == r) { t[v] = x; return; }
int m = (l + r) / 2;
if (i <= m) update(2 * v, l, m, i, x);
else update(2 * v + 1, m + 1, r, i, x);
t[v] = max(t[2 * v], t[2 * v + 1]);
}
int main() {
int q;
cin >> n >> q;
a.resize(n);
t.assign(4 * n, 0);
for (auto &x : a) cin >> x;
build(1, 0, n - 1);
while (q--) {
char type; int x; long long y;
cin >> type >> x >> y;
if (type == 'B') {
a[x - 1] += y;
update(1, 0, n - 1, x - 1, a[x - 1]);
} else {
cout << query(1, 0, n - 1, x - 1, (int)y - 1) << "\n";
}
}
return 0;
}