Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
b_kasenov47
14 / 14 / 1
Регистрация: 28.07.2012
Сообщений: 57
#1

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

28.07.2012, 20:36. Просмотров 1426. Ответов 4
Метки нет (Все метки)

Дана такая задача:
есть трехмерное пространство. Поступают запросы вида увеличить количество элементов в параллелепипеде от 0, 0, 0 до x, y, z на val, и посчитать сумму в параллелепипеде от x, y, z до x1, y1, z1. Вроде бы все ясно - пишется трехмерное дерево Фенвика, но при подсчете суммы (2 запрос) Какие-то косяки (возможно в том месте, которое похоже на принцип включения-исключения). Тестирующая системы выдает ВА. Помогите, кто может!!! Вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 минут
Да ладно люди!!! Столько просмотров, и никто помочь не может????
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.07.2012, 20:36     3-х мерное дерево Фенвика
Посмотрите здесь:

дерево C++
C++ Дерево...
C++ B-дерево
C++ Дерево
C++ Дерево
C++ Дерево
C++ дерево
C++ N мерное дерево
C++ Дерево, бинарное дерево
N-дерево C++
C++ Дерево дерево, странное дерево
C++ Дерево

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Intel~lect
135 / 124 / 2
Регистрация: 03.07.2012
Сообщений: 355
28.07.2012, 20:42     3-х мерное дерево Фенвика #2
Попробую предположить. Потому что даже не знаю что такое дерево Фенвика и как оно рассчитывается
Цитата Сообщение от b_kasenov47 Посмотреть сообщение
int ans = a + b - c + d;
Здесь возможно вместо плюс минус поставил или скобки пропущены. Ведь эта функция сумму рассчитывает.
b_kasenov47
14 / 14 / 1
Регистрация: 28.07.2012
Сообщений: 57
28.07.2012, 21:45  [ТС]     3-х мерное дерево Фенвика #3
Подробнее о нем можно узнать на http://e-maxx.ru/algo/fenwick_tree. Но там лишь одномерный случай. ф-ция sum которая принимает 3 аргумента возвращает значение суммы в параллелепипеде от (0, 0, 0) до (x, y, z). т.е. надо что-то вычитать а что-то добавлять. т.е для одномерного случая, чтобы узнать сумму от L до R надо sum(R) - sum(L-1)
User1990
26 / 26 / 2
Регистрация: 03.11.2009
Сообщений: 158
28.07.2012, 23:39     3-х мерное дерево Фенвика #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;
нельзя вовращать значение локальной переменной, её может затереть , лучше в формальных параметрах заведи ещё одну переменную в нею и вноси результт
b_kasenov47
14 / 14 / 1
Регистрация: 28.07.2012
Сообщений: 57
29.07.2012, 12:21  [ТС]     3-х мерное дерево Фенвика #5
Цитата Сообщение от User1990 Посмотреть сообщение
нельзя вовращать значение локальной переменной, её может затереть , лучше в формальных параметрах заведи ещё одну переменную в нею и вноси результт
не помогло((( да и перед этим я такие вещи (возврат локальной переменной) много раз делал. работало.

Добавлено через 11 часов 55 минут
Люди, помогите же! Очень надо!
Yandex
Объявления
29.07.2012, 12:21     3-х мерное дерево Фенвика
Ответ Создать тему
Опции темы

Текущее время: 19:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru