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

Куча, дерево отрезков. Прибавление на отрезке, нахождение сумма на отрезке - C++

Восстановить пароль Регистрация
 
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
07.05.2013, 18:46     Куча, дерево отрезков. Прибавление на отрезке, нахождение сумма на отрезке #1
Написал вот класс Кучки. Сейчас она может увеличить значения всех элементов на отрезке l - r на величину c (время O(logN)), а так же выдать значение элемента с индексом idx (O(logN)). Видимо, сделал я её не стандартно, так как придумывал сам во время олимпиады, а теперь захотелось немного доработать её и добавить функцию суммы на отрезке l - r и тоже за время O (logN). Help.
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
28
29
30
31
32
33
34
35
36
37
38
39
template <typename E>
class THeap {
private:
    vector <E> heap;
    int n;
 
    void hp_add(int l, int r, E c) {
        if (l > r)
            return;
        if (l%2 == 0) {
            heap[l] += c;
            l++;
        }
        if (r%2 == 1) {
            heap[r] += c;
            r--;
        }
        hp_add((l-1)/2, (r/2)-1, c);
    }
 
    E hp_get(int idx) {
        if (idx == 0) 
            return heap[0];
        if (idx%2 == 0) 
            return heap[idx] + hp_get((idx/2)-1);   
        return heap[idx] + hp_get((idx-1)/2);
    }
public:
    THeap(int _n, E c) {
        n = _n;
        heap = vector <E> (2*n-1, c);
    }
    void add(int l, int r, E c) {
        hp_add(l + n - 1, r + n - 1, c);
    }
    E get(int idx) {
        return hp_get(idx + n - 1);
    }
};
Добавлено через 1 минуту
Примерчик.
C++
1
2
3
4
THeap<long long> hp(5, 0);
hp.add(2, 3, 2);
hp.add(3, 4, 1);
long long c = hp.get(3);
Добавлено через 14 часов 59 минут
..up..

Добавлено через 57 минут
--up--

Добавлено через 3 часа 29 минут
$$ up $$
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.05.2013, 18:46     Куча, дерево отрезков. Прибавление на отрезке, нахождение сумма на отрезке
Посмотрите здесь:

C++ Непрерывные функции и нахождение минимума на отрезке
Нахождение корня в заданном отрезке C++
C++ Вычислить 18 значений функции ax^2+bx+c на отрезке [e,f], сохранить их в массиве Y и определить, имеет ли уравнение ax^2+bx+c=0 на отрезке [e,f] по крайней мере хотя бы один корень.
C++ Найти количество отрезков B, размещенных на отрезке A
C++ Даны целые положительные числа А и B. Найти количество отрезков В, размещенных на отрезке А
C++ Нахождение суммы на отрезке
C++ Найти на отрезке все числа, сумма цифр которых дает заданное
C++ Нахождение суммы значений функции у=х*х на отрезке 1,5 с шагом 1

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему

Метки
дерево отрезков, куча
Опции темы

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