Дерево Фенвика + Sparse Table ~ Сириус 07.06

Дерево Фенвика

Дерево Фенвика - структура данных, дерево на одномерном массиве, которая обладает такими свойствами, как:

Сумма на отрезке с L по R
Изменение значения в какой-то позиции за O(LogN)
Требует O(N) памяти

Код:

ll n;
vector<ll> sum;

ll get_sum(ll i){ //сумма
    ll ans = 0;
    for(; i >= 0; i = (i&(i+1))-1){
        ans += sum[i];
    }
    return ans;
}

void update(ll i, ll x){ //обновление на точке
    for(; i < n; i = (i | (i+1))){
        sum[i] += x;
    }
}

ll sum_otr(ll l, ll r){
    return get_sum(r) - get_sum(l-1);
}

Так же можно сделать MAX на отрезке, но это извращение, проще написать ДО

Двумерное Дерево Фенвика

Аналогично

Код (скорее всего с багами):

ll n;
vector<vector<ll>> f(MAXN, vector<ll>(MAXN));


ll get_sum(int i, int j){
    int r = 0;
    while(j > 0){
        int k = i;
        while(k > 0){
            r += f[k][j];
            k -= k & -k;
        }
        j = j & -j;
    }
    return r;
}


ll sum(int x1, int y1, int x2, int y2){
    return get_sum(x2, y2) - get_sum(x1, y2) - get_sum(x2, y1) + get_sum(x1, y1);
}

void add(int i, int j, int x){
    while(j <= n){
        int k = i;
        while(k <= n){
            f[k][j] += x;
            k += k & (~k);
        }
        j += j & (~j);
    }
}

Sparse Table

Sparse Table - структура данных, позволяющая находить минимум на отрезке

#define MAX 100010
#define LOGMAX 30

ll n;
vector <ll> arr;
vector <vector<ll>> Sparce(MAX, vector<ll>(LOGMAX));

ll task(ll l, ll r) {
    ll j = (ll) log2(r - l + 1);
    if (Sparce[l][j] <= Sparce[r - (1 << j) + 1][j]) {
        return Sparce[l][j];
    }
    return Sparce[r - (1 << j) + 1][j];
}

...
в функции main 
for (ll i = 0; i < n; i++) {
    Sparce[i][0] = arr[i];
}
for (ll j = 1; (1 << j) <= n; j++) {
    for (ll i = 0; (i + (1 << j) - 1) < n; i++) {
        if (Sparce[i][j - 1] < Sparce[i + (1 << (j - 1))][j - 1]) {
            Sparce[i][j] = Sparce[i][j - 1];
        } else {
            Sparce[i][j] = Sparce[i + (1 << (j - 1))][j - 1];
        }
    }
}

Оптимизация:

#define MAX 100010
#define LOGMAX 30
ll n;
vector <ll> arr;
vector <vector<ll>> Sparce(LOGMAX, vector<ll>(MAX));

ll task(ll l, ll r) {
    ll j = (ll) log2(r - l);
    return min(Sparce[j][l], Sparce[j][r - (1 << j)]);
}


int main() {
    for (ll i = 0; i < n; i++) {
        Sparce[0][i] = arr[i];
    }
    for (ll j = 0; j < LOGMAX - 1; j++) {
        for (ll i = 0; i + (2 << j) <= n; i++) {
            Sparce[j + 1][i] = min(Sparce[j][i], Sparce[j][i + (1 << j)]);
        }
    }
}

Disjoint Sparse Table

Sparse Table не мог быть построен для тех функций от подотрезка массива, для которых каждое число подотрезка должно быть учтено ровно один раз. Disjoint Sparse Table решает эту проблему и с предподсчётом за O(nlogn) позволяет в онлайне за O(1) находить почти любые функции от подотрезка, например кол-во минимумов, или произведение по непростому модулю. ~ wiki.algocode.ru

Основная идея: разделяй и властвуй

TODO: написать дальше, автор конспекта закрыл ноут и пошел внимательно слушать

Ссылки данной штуки: https://algorithmica.org/ru/sparse-table, https://wiki.algocode.ru/index.php?title=Disjoint_Sparse_Table