3-х мерное дерево Фенвика

@b_kasenov47 · Регистрация: 28.07.2012

Студворк — интернет-сервис помощи студентам

Дана такая задача:
есть трехмерное пространство. Поступают запросы вида увеличить количество элементов в параллелепипеде от 0, 0, 0 до x, y, z на val, и посчитать сумму в параллелепипеде от x, y, z до x1, y1, z1. Вроде бы все ясно - пишется трехмерное дерево Фенвика, но при подсчете суммы (2 запрос) Какие-то косяки (возможно в том месте, которое похоже на принцип включения-исключения). Тестирующая системы выдает ВА. Помогите, кто может!!! Вот код:

C++

void add(int val, int x, int y, int z)
{
    for (int i = x; i < n; i = i | (i + 1))
        for (int j = y; j < n; j = j | (j + 1))
            for (int k = z; k < n; k = k | (k + 1))
                a[i][j][k] += val; 
}
 
int sum(int x, int y, int z)
{
    int ans = 0;
    for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
        for (int j = y; j >= 0; j = (j & (j + 1)) - 1)
            for (int k = z; k >= 0; k = (k & (k + 1)) - 1)
                ans += a[i][j][k];
    return ans;
}
 
int sum(int x, int y, int z, int x2, int y2, int z2)
{
    int a = sum (x2, y2, z2);
    int b = sum (x - 1, y - 1, z - 1);
    int c = sum (x2, y2, z - 1) + sum (x2, y - 1, z2) + sum (x - 1 ,y2, z2);
    int d = sum (x - 1, y - 1, z2) + sum (x - 1, y2, z - 1) + sum (x2, y - 1, z - 1);
    int ans = a + b - c + d;
    return ans; 
}

Добавлено через 2 часа 29 минут
Да ладно люди!!! Столько просмотров, и никто помочь не может????

@Intel~lect · 28.07.2012, 20:42

Попробую предположить. Потому что даже не знаю что такое дерево Фенвика и как оно рассчитывается

Сообщение от b_kasenov47

int ans = a + b - c + d;

Здесь возможно вместо плюс минус поставил или скобки пропущены. Ведь эта функция сумму рассчитывает.

@b_kasenov47 · 28.07.2012, 21:45 **[ТС]**

Подробнее о нем можно узнать на http://e-maxx.ru/algo/fenwick_tree. Но там лишь одномерный случай. ф-ция sum которая принимает 3 аргумента возвращает значение суммы в параллелепипеде от (0, 0, 0) до (x, y, z). т.е. надо что-то вычитать а что-то добавлять. т.е для одномерного случая, чтобы узнать сумму от L до R надо sum(R) - sum(L-1)

@User1990 · 28.07.2012, 23:39

Сообщение от b_kasenov47

int ans = 0; for (int i = x; i >= 0; i = (i & (i + 1)) - 1) for (int j = y; j >= 0; j = (j & (j + 1)) - 1) for (int k = z; k >= 0; k = (k & (k + 1)) - 1) ans += a[i][j][k]; return ans;

нельзя вовращать значение локальной переменной, её может затереть , лучше в формальных параметрах заведи ещё одну переменную в нею и вноси результт

@b_kasenov47 · 29.07.2012, 12:21 **[ТС]**

Сообщение от User1990

нельзя вовращать значение локальной переменной, её может затереть , лучше в формальных параметрах заведи ещё одну переменную в нею и вноси результт

не помогло((( да и перед этим я такие вещи (возврат локальной переменной) много раз делал. работало.

Добавлено через 11 часов 55 минут
Люди, помогите же! Очень надо!

@Intel~lect 137 / 126 / 14 Регистрация: 03.07.2012 Сообщений: 355
	28.07.2012, 20:42	2
	Попробую предположить. Потому что даже не знаю что такое дерево Фенвика и как оно рассчитывается Сообщение от b_kasenov47 int ans = a + b - c + d; Здесь возможно вместо плюс минус поставил или скобки пропущены. Ведь эта функция сумму рассчитывает. 0

@b_kasenov47 14 / 14 / 3 Регистрация: 28.07.2012 Сообщений: 57
	28.07.2012, 21:45 [ТС]	3
	Подробнее о нем можно узнать на http://e-maxx.ru/algo/fenwick_tree. Но там лишь одномерный случай. ф-ция sum которая принимает 3 аргумента возвращает значение суммы в параллелепипеде от (0, 0, 0) до (x, y, z). т.е. надо что-то вычитать а что-то добавлять. т.е для одномерного случая, чтобы узнать сумму от L до R надо sum(R) - sum(L-1) 0

@User1990 26 / 26 / 11 Регистрация: 03.11.2009 Сообщений: 158
	28.07.2012, 23:39	4
	Сообщение от b_kasenov47 int ans = 0; for (int i = x; i >= 0; i = (i & (i + 1)) - 1) for (int j = y; j >= 0; j = (j & (j + 1)) - 1) for (int k = z; k >= 0; k = (k & (k + 1)) - 1) ans += a[i][j][k]; return ans; нельзя вовращать значение локальной переменной, её может затереть , лучше в формальных параметрах заведи ещё одну переменную в нею и вноси результт 0

@b_kasenov47 14 / 14 / 3 Регистрация: 28.07.2012 Сообщений: 57
	29.07.2012, 12:21 [ТС]	5
	Сообщение от User1990 нельзя вовращать значение локальной переменной, её может затереть , лучше в формальных параметрах заведи ещё одну переменную в нею и вноси результт не помогло((( да и перед этим я такие вещи (возврат локальной переменной) много раз делал. работало. Добавлено через 11 часов 55 минут Люди, помогите же! Очень надо! 0

Опции темы