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

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

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

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

28.07.2012, 20:36. Просмотров 1458. Ответов 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-х мерное дерево Фенвика
Посмотрите здесь:

N мерное дерево - C++
Добый день есть неработающая функция создания n дерева ходов игры, проблема такая она не выделяет память под след элемент когда i=1,2,...

Дерево - C++
Нужно НЕ рекурсивно распечатать двоичное дерево по слоям, собственно как это сделать?

B-дерево - C++
Есть у кого реализация B-дерева на Си? хотя бы добавление и удаление)))) А то есть на Паскале, но перевести это для меня нереально)

Дерево - C++
Здравствуйте!Никак не могу разобраться с двумя заданиями. http://prntscr.com/9924ty - задание 1 http://prntscr.com/9924ys и вот к...

Дерево... - C++
в общем есть дерево двоичного поиска, состоит из функций добавления, удаления, поиска, вывода, ф-ция, которая выводит размер дерева... К...

N-дерево - C++
Дано N-дерево. Найти поддерево не включающее ни одну из заданных вершин. Вообще хотя бы &quot;Дано N-дерево&quot; - если вы кинете готовый код...

дерево - C++
// derevo_lr2.cpp : Defines the entry point for the console application. #include &quot;stdafx.h&quot; #include &quot;iostream&quot; using namespace std;...

Дерево - C++
Условие: Программа построения дерева, где узел(корень) - ФИО препода, а инф. поля (наверное левая\правая ветки) имеют записи:...

дерево - C++
Сделал дерево, если его ветви создаются на стадии компиляции, то все работает нормально, но если их создает пользователь, то все ветви...

Дерево - C++
Здравствуйте! Есть вот такая задача: Условия: Определить структуру бинарного дерева поиска и разработать функции, которые необходимы...

Дерево - C++
Добрый вечер)))) Вот сегодне &quot;изучали &quot;деревья&quot;)) Дали задание: &quot;Написать программу копирования вершин, связанных с правым...

Двоичное дерево - 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-х мерное дерево Фенвика
Ответ Создать тему
Опции темы

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