Варианты дерева Фенвика

Одномерное дерево Фенвика

int a[MAX_SIZE];

int alpha(int x) {
    int res = 0;
    for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
        res += a[i];
    return res;
}

void modifyAlphas(int x, int val) {
    for (int i = x; i < MAX_SIZE; i |= i + 1)
        a[i] += val;
}

Запрос суммы на отрезке, изменение отдельных элементов

alpha(x) — сумма элементов от 0-го до x-го.

int sum(int x) {
    return alpha(x);
}

void add(int x, int val) {
    modifyAlphas(x, val);
}

Запрос значений отдельных элементов, изменение на отрезке

alpha(x) — значение x-го элемента.

int get(int x) {
    return alpha(x);
}

void add(int l, int r, int val) {
    modifyAlphas(l, val);
    modifyAlphas(r + 1, -val);
}

Запрос суммы на отрезке, изменение на отрезке

beta(x) * x + alpha(x) — сумма элементов от 0-го до x-го.

int sum(int x) {
    return beta(x) * x + alpha(x);
}

void add(int l, int r, int val) {
    modifyBetas(l, val);
    modifyAlphas(l, val * (-l + 1));
    modifyBetas(r + 1, -val);
    modifyAlphas(r + 1, val * r);
}

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

int a[MAX_SIZE][MAX_SIZE];

int alpha(int x, int y) {
    int res = 0;
    for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
        for (int j = y; j >= 0; j = (j & (j + 1)) - 1)
            res += a[i][j];
    return res;
}

void modifyAlphas(int x, int y, int val) {
    for (int i = x; i < MAX_SIZE; i |= i + 1)
        for (int j = y; j < MAX_SIZE; j |= j + 1)
            a[i][j] += val;
}

Запрос суммы на прямоугольнике, изменение отдельных элементов

alpha(x, y) — сумма элементов от (0; 0)-го до (x; y)-го.

int sum(int x, int y) {
    return alpha(x, y);
}

void add(int x, int y, int val) {
    modifyAlphas(x, y, val);
}

Запрос значений отдельных элементов, изменение на прямоугольнике

alpha(x, y) — значение (x; y)-го элемента.

int get(int x, int y) {
    return alpha(x, y);
}

void add(int lx, int rx, int ly, int ry, int val) {
    modifyAlphas(lx, ly, val);
    modifyAlphas(lx, ry + 1, -val);
    modifyAlphas(rx + 1, ly, -val);
    modifyAlphas(rx + 1, ry + 1, val);
}

Запрос суммы на прямоугольнике, изменение на прямоугольнике

delta(x, y) * x * y + gamma(x, y) * y + beta(x, y) * x + alpha(x, y) — сумма элементов от (0; 0)-го до (x; y)-го.

int sum(int x, int y) {
    return delta(x, y) * x * y + gamma(x, y) * y + beta(x, y) * x + alpha(x, y);
}

void add(int lx, int rx, int ly, int ry, int val) {
    modifyDeltas(lx, ly, val);
    modifyGammas(lx, ly, val * (-lx + 1));
    modifyBetas(lx, ly, val * (-ly + 1));
    modifyAlphas(lx, ly, val * (-lx + 1) * (-ly + 1));

    modifyDeltas(lx, ry + 1, -val);
    modifyGammas(lx, ry + 1, -val * (-lx + 1));
    modifyBetas(lx, ry + 1, val * ry);
    modifyAlphas(lx, ry + 1, val * (-lx + 1) * ry);

    modifyDeltas(rx + 1, ly, -val);
    modifyGammas(rx + 1, ly, val * rx);
    modifyBetas(rx + 1, ly, -val * (-ly + 1));
    modifyAlphas(rx + 1, ly, val * rx * (-ly + 1));

    modifyDeltas(rx + 1, ry + 1, val);
    modifyGammas(rx + 1, ry + 1, -val * rx);
    modifyBetas(rx + 1, ry + 1, -val * ry);
    modifyAlphas(rx + 1, ry + 1, val * rx * ry);
}

Ссылки

• Дерево Фенвика
• Дерево Фенвика с модификацией на отрезке
• Mishra P. A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays