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

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

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

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

28.07.2012, 20:36. Просмотров 1490. Ответов 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 минут
Да ладно люди!!! Столько просмотров, и никто помочь не может????
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.07.2012, 20:36
Здравствуйте! Я подобрал для вас темы с ответами на вопрос 3-х мерное дерево Фенвика (C++):

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

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой - C++
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

Дано дерево. Распечатать дерево по уровням - C++
Дано дерево. Распечатать дерево по уровням.

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру - C++
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру. вот...

Напишите программу, которая бы читала дерево в формате (а) и затем печатала бы это дерево в формате (б). - C++
Представление дерева: а) Д (Б (А, Ф (В,)), Е (,З (Ж, И))) б) Д Б А Ф ...

Дерево дерево, странное дерево - C++
Нужна помощь в построении дерева. Задание таково: Вершина дерева содержит N целых значений и два указателя на потомков. Запись значений...

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

Добавлено через 11 часов 55 минут
Люди, помогите же! Очень надо!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.07.2012, 12:21
Привет! Вот еще темы с ответами:

Дерево, бинарное дерево - C++
Читаю про дерево и не до конца понимаю, а точнее понимаю, но вопрос в том, правильно ли я понимаю, надеюсь вы мне подскажите. Вот есть...

Двумерное дерево отрезков или фенвика + сканирующая прямая - Алгоритмы
Интересно было бы порешать задачи на эту тему, киньте что-нибудь

Функция Фенвика - PascalABC.NET
Нельзя использовать циклы, условные инструкции, вызовы функций (то есть любые нелинейные конструкции в алгоритмах), арифметические операции...

Функия Фенвика - Turbo Pascal
Значением функции Фенвика для числа N называется максимальная степень двойки, на которую нацело делится число N. Дано число N. Определить...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
29.07.2012, 12:21
Ответ Создать тему
Опции темы

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