The following task is given: an array of integer $$$a_1, \ldots, a_n$$$ is given, as well as $$$q$$$ queries of one of two types:

1. $$$a_i+=x$$$, where $$$l \leq i \leq r$$$.
2. find out the number of indexes $$$i$$$, where $$$l\leq i\leq r$$$ and $$$a_j < a_i$$$, for all $$$j:$$$ $$$l \le j < i$$$. (Or humanly — the number of prefix maxima on the segment)

We want to solve this faster than for $$$O(sqrt(n))$$$ per request.

Let's consider an easier option when we don't have change requests. Then we can make a just Segment Tree, where a sorted list of prefix maxima is stored at the vertex, if our segment is the segment corresponding to the vertex of the segment tree. Then we should just make an algorithm, anological Merge Sort Tree, only we should consider the vertices into which we split the query from left to right and store the maximum among the previous elements on a suitable segment, and add to the answer the number of elements in the vertex larger than the maximum before, and then update the maximum.

It works for $$$O(log(n)^2)$$$ per request, as well as $$$O(n log(n))$$$ memory and time to build.

Note that this can be redone so that there are change requests. Then we only need to learn how to combine such lists and add value to them. And for this, for example, a persistent treap is suitable. Then we will store a persistent treap of all prefix maxima at the vertex. Then, when updating, if the vertex segment lies completely inside the query, then we will simply add the desired value to our treap (well, of course, we will push this value down). And to combine the lists, you just need to copy the values from the left subtree, and also select the desired suffix from the right subtree and copy it as well, and then combine these trees.

This already works for $$$O(log(n)^2)$$$ per request, but in this case there will be build for $$$O(nlog(n)^2)$$$, and, most importantly, memory will be $$$O((n +q)log(n)^2)$$$ at total.

Now the normal solution is for $$$O(n)$$$ memory and $$$O(log(n)^2)$$$ per request.

Let there be a just tree segment (the vertex $$$v$$$ has a left subtree — this is $$$v.l$$$, and the right one is $$$v.r$$$), then let us, for each vertex $$$v$$$, learn to count two values $$$cnt_v$$$ — the number of prefix maxima, if our segment is the segment corresponding to the vertex $$$v$$$, and $$$max_v$$$ is the maximum on the same segment.

Then we implement the function $$$f(v, x)$$$, which will count the number of prefix maxima of strictly large $$$x$$$ on the segment of the vertex $$$v$$$.

We have only three cases:

1. If $$$v$$$ is a leaf, then everything is simple, you need to compare the value of this element with $$$x$$$.
2. If $$$x\geq max_{v.l}$$$, then note that there are no exactly finding elements in the left subtree (since they are less than or equal to $$$x$$$), then we are only interested in the right subtree, that is, $$$f(v, x) = f(v.r, x)$$$.
3. If $$$x <max_{v.l}$$$, then we are no longer interested in the value of $$$f(v.r, x)$$$, since the element with the value $$$max_{v.l}$$$ will definitely be among in the prefix maxima, so the number of prefix maxima on the right will be the same as and in the absence of a limit on $$$x$$$, and we already know this number — this is $$$cnt_v - cnt_{v.l}$$$, since we need the number of maxima on the right, and that's all except those on the left (logical, isn't it) (and it's not $$$cnt_{v.l}$$$, since in this case there may be elements less than $$$max_{v.l}$$$). So $$$f(v, x) = f(v.l, x) + cnt_v - cnt_{v.l}$$$.

This function works for $$$O(log(n))$$$, since each time we descend into exactly one subtree, and the depth of the tree of segments is just the logarithm.

It is clear that it is easy to solve the problem with this function, we can solve the problem, just like in the first case, only we will need to do not $$$lowerbound$$$ according to the list, but simply run this function. Building and the like is also trivial with this function. (All the subtleties can be found in the code)

#include <iostream>
#include <vector>
 
using namespace std;
 
const int N = (1 << 19);
 
pair<int, int> t[2 * N]; // сnt, maximum
int mod[2 * N];
bool its_leaf[2 * N];
 
void push(int v) {
    t[v * 2 + 1].second += mod[v];
    t[v * 2].second += mod[v];
    mod[v * 2 + 1] += mod[v];
    mod[v * 2] += mod[v];
    mod[v] = 0;
}
 
int f(int v, int w) {
    if (its_leaf[v]) {
        if (t[v].second > w)
            return 1;
        return 0;
    }
 
    push(v);
    int r = v * 2, l = v * 2 + 1;
    if (t[l].second >= w)
        return f(r, w);
    else
        return f(l, w) + t[v].first - t[l].first;
}
 
void update(int v, int l, int r, int L, int R, int val) {
    if (R <= l || r <= L)
        return;
    if (L <= l && r <= R) {
        t[v].second += val;
        mod[v] += val;
        return;
    }
 
    push(v);
    int m = (l + r) / 2;
    update(v * 2 + 1, l, m, L, R, val);
    update(v * 2, m, r, L, R, val);
    t[v].first = t[v * 2 + 1].first + f(v * 2, t[v * 2 + 1].second);
    t[v].second = max(t[v * 2 + 1].second, t[v * 2].second);
}
 
void build(int v, int l, int r, vector<int> &a) {
    if (r - l == 1) {
        its_leaf[v] = 1;
        t[v] = make_pair(1, a[l]);
        return;
    }
 
    int m = (l + r) / 2;
    build(v * 2 + 1, l, m, a);
    build(v * 2, m, r, a);
    t[v].first = t[v * 2 + 1].first + f(v * 2, t[v * 2 + 1].second);
    t[v].second = max(t[v * 2 + 1].second, t[v * 2].second);
}
 
pair<int, int> get(int v, int l, int r, int L, int R, int max_val) { // ans, max_val
    if (R <= l || r <= L)
        return {0, max_val};
    if (L <= l && r <= R)
        return {query(v, max_val), max(t[v].second, max_val)};
 
    push(v);
    int m = (l + r) / 2;
    auto z1 = get(v * 2 + 1, l, m, L, R, max_val);
    auto z2 = get(v * 2, m, r, L, R, z1.second);
    return {z1.first + z2.first, max(z1.second, z2.second)};
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int q;
    cin >> q;
    build(1, 0, n, a);
 
    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;
        if (t == 1) {
            cout << get(1, 0, n, l - 1, r, -n).first << '\n';
        } else {
            int val;
            cin >> val;
            update(1, 0, n, l - 1, r, val);
        }
    }
}

Also thanks to Um_nik, who, in fact, came up with the last solution in a problem that boiled down to this and made it much more interesting)))

As well as examples of tasks for this technique 1, 2.