Дана следующая задача: дан массив целых чисел $$$a_1, \ldots, a_n$$$, а также $$$q$$$ запросов одного из двух видов:

1. $$$a_i += x$$$, где $$$l \leq i \leq r$$$.
2. узнать количество индексов $$$i$$$, где $$$l \leq i \leq r$$$ и $$$a_j < a_i$$$, для всех $$$j:$$$ $$$l \leq j < i$$$. (Или по-человчески — количество префиксных максимумов на отрезке)

Очень хочется это решать быстрее, чем за $$$O(sqrt(n))$$$ на запрос.

Рассмотрим более легкий вариант, когда у нас нет запросов изменения. Тогда можно просто сделать Дерево отрезков, где в вершине хранится отсортированный список префиксных максимумов, если наш отрезок — это отрезок, соответствующий вершине дерева отрезков. Тогда мы должны просто сделать алгоритм, анологичный Merge Sort Tree, только мы должны в запросе вершины, на которые мы разбиваем разбиваем запрос, рассматривать слева направо и хранить максимум среди предыдущих элементов на подходящем отрезке, и к ответу прибавлять количество элементов в вершине, больших максимума до этого, а затем обновить максимум.

Это работает за $$$O(log(n)^2)$$$ на запрос, а также $$$O(nlog(n))$$$ памяти и времени на построение.

Заметим, что это можно переделать, чтобы были запросы изменения. Тогда нам нужно только научиться объединять такие списки и прибавлять к ним значение. А для этого подходит, например, персистентное декартво дерево. Тогда мы в вершине будем хранить персистентное декартово дерево из всех префиксных максимумов. Тогда при обновлении, если отрезок вершины лежит полностью внутри запроса, то просто добавим в наше декартово дерево нужное значение (ну и понятное дело, пропушим вниз это значение). А для объединения списков нужно просто скопировать значения из левого поддерева, а также выбрать нужный суффикс из правого поддерева и его также скопировать, а затем объеденить эти деревья.

Это уже работает за $$$O(log(n)^2)$$$ на запрос, но в этом случае будет построение за $$$O(nlog(n)^2)$$$, а, что самое главное, памяти будет $$$O((n + q)log(n)^2)$$$ суммарно, что пихать, конечно же, не очень хочется.

Теперь нормальное решение за $$$O(n)$$$ памяти и $$$O(log(n)^2)$$$ на запрос.

Пусть есть самое обычное дерево отрезок (У вершины $$$v$$$ есть левое поддерево — это $$$v.l$$$, а правое — это $$$v.r$$$), тогда пусть, мы для каждой вершины $$$v$$$ научились считать две величины $$$cnt_v$$$ — количество префиксных максимумов, если наш отрезок — это отрезок соответствующий вершине $$$v$$$, и $$$max_v$$$ — это максимум на том же отрезке.

Тогда реализуем функцию $$$f(v, x)$$$, которая будет считать количество префиксных максимумов строго больших $$$x$$$ на отреке вершины $$$v$$$.

У нас есть всего три случая:

1. Если $$$v$$$ — это лист, то все просто, нужно сравнить значение у этого элемента с $$$x$$$.
2. Если $$$x \geq max_{v.l}$$$, тогда заметим, что в левом поддереве нет точно подходящих элементов (так как они меньше или равны $$$x$$$), тогда нам интересно только правое поддерево, то есть $$$f(v, x) = f(v.r, x)$$$.
3. Если $$$x < max_{v.l}$$$, тогда нам уже не интересно значение $$$f(v.r, x)$$$, так как элемент со значением $$$max_{v.l}$$$ точно будет среди префиксных максимумов, значит количество префиксных максимумов справа будет такое же, как и в случае отсутствия ограничения на $$$x$$$, а это количество мы уже знаем — это $$$cnt_v - cnt_{v.l}$$$, так как нам нужно количество максимумов справа, а это все, кроме тех, кто слева (логично, не правда-ли) (и это не $$$cnt_{v.l}$$$, так как в этом случае могут быть элементы меньше $$$max_{v.l}$$$). Значит $$$f(v, x) = f(v.l, x) + cnt_v - cnt_{v.l}$$$.

Эта функция работает за $$$O(log(n))$$$, так как каждый раз мы спускаемся ровно в одно поддерева, а глубина дерева отрезков как раз логарифм.

Понятно, что с этой функцией решать задачу легко, мы можем решать задачу, также, как и в первом случае, только нам нужно будет сделать не $$$lowerbound$$$ по списку, а просто запустить эту функцию. Построение и тому подобное также тривиально с этой функцией. (Все тонкости можно посмотреть в коде, вроде, он понятно написан)))

#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);
        }
    }
}

Также спасибо Um_nik, который, собственно, придумал последнее решение в задаче, которая сводилась к этому и сделал ее значительно интереснее)))

А также примеры задач на эту технику 1, 2.