Варианты дерева Фенвика
Перейти к навигации
Перейти к поиску
Одномерное дерево Фенвика
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);
}