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

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

Войти
Регистрация
Восстановить пароль
 
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
#1

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

07.05.2013, 18:46. Просмотров 1131. Ответов 0

Написал вот класс Кучки. Сейчас она может увеличить значения всех элементов на отрезке 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 $$
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.05.2013, 18:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Куча, дерево отрезков. Прибавление на отрезке, нахождение сумма на отрезке (C++):

Дерево отрезков. Поиск суммы чисел на отрезке массива. Изменение всех чисел на отрезке массива - C++
Добрый день, помогите пож-та решить задачу на с++.И если возможно ,то с объяснением.

Найти количество отрезков B, размещенных на отрезке A - C++
Задания: 4) Даны положительные числа A и B (A &gt; B). На отрезке длины A размещено максимально возможное количество отрезков длины B...

Даны целые положительные числа А и B. Найти количество отрезков В, размещенных на отрезке А - C++
Даны целые положительные числа А и В (А&gt;В). На отрезке длины А размещено максимально возможное кол-во орезков длины В(без наложений)....

Не используя операции умножения и деления, найти количество отрезков, расположенных на отрезке А - C++
Прошу еще раз, прочитайте правила форума: http://www.cyberforum.ru/announcement.php?a=3. В особенности пункт 4.3: Создавайте темы с...

Используя операцию деления нацело, найти количество отрезков B, размещенных на отрезке A - C++
Даны целые положительные числа A и B (A &gt; B). На отрезке длины A размещено максимально возможное количество отрезков длины B (без...

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

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.05.2013, 18:46
Привет! Вот еще темы с ответами:

Нахождение суммы на отрезке - C++
помогите с задачей написать программу нахождения суммы значений функции y=x*x на отрезке с шагом 1 срочно надо !! Нужно решение...

Нахождение простых чисел на отрезке [m;n] - C++
INPUT.TXT содержит два натуральных числа M и N, разделенных пробелом (2 ≤ M ≤ N ≤ 106). В выходной файл OUTPUT.TXT выведите все простые...

Нахождение корня в заданном отрезке - C++
Здравствуйте! Собственно, нужно найти корень нелинейного уравнения из заданного отрезка с точностью до eps=0.01, используя метод итераций. ...

Непрерывные функции и нахождение минимума на отрезке - C++
Помогите реализовать функцию Solve из данной задачи: Задается непрерывная функция f(x). Требуется на интервале с заданной точностью E...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

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