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

Дерево отрезков - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Длинное сложение http://www.cyberforum.ru/cpp-beginners/thread630876.html
Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все алгоритмы, процедуры подсчета и т. д.), но сложность состоит в том, что я не понимаю строищихся структур и вообще никогда не программировал на c++.Поэтому прошу помочь собрать все воедино (чтение из файла, работа программы, запись в файл). Основная задача - считать с файла, воспользоваться функцией, вывести в файл ...
C++ Алгоритм Дейкстры Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все алгоритмы, процедуры подсчета и т. д.), но сложность состоит в том, что я не понимаю строищихся структур и вообще никогда не программировал на c++.Поэтому прошу помочь собрать все воедино (чтение из файла, работа программы, запись в файл). Основная задача - считать с файла, воспользоваться функцией, вывести в файл... http://www.cyberforum.ru/cpp-beginners/thread630873.html
C++ Dev-C++ 4.9.9.2 не показывает номера строк
Чё делать? +++++++++++++++++++++++++++++++++++++++ Я в неё интегрировал g++ 4.6.1 по-моему, вот инсталлятор mingw-get-inst-20111118.exe (пользовался им и раньше, всё было нормально) Инсталлятор качает чего-то с сайта, обновления, наверное. И теперь ошибки стали выводиться на русском языке, а номера строк, где эти ошибки есть, не выводятся. Добавлено через 5 часов 17 минут Парни, вы...
C++ Делаю Memory Manager Array с простым (int) exception последний элемент чудит
//array_hpp #ifndef Array_HPP #define Array_HPP #include "Point.hpp" #include <iostream> class Array {
C++ "Плейсхолдер" (placeholder) http://www.cyberforum.ru/cpp-beginners/thread630846.html
"Плейсхолдер" (переводится как прототип или заполнитель ?) - так говорят многие участники на этом форуме, объясните пожалуйста, что это такое ?? поисковик выдал мне много всего от хабра с html5 до как лечить удава. Ребят, еще вопрос у меня в теме по Си )) про signal.h, помогите разобраться ))
C++ Рисование ASCII кодами и русский текст в консоли Всем добрый вечер. И вот такой вопрос есть. Сначала печатаю в консоли текст а под ним горизонтальную линию. Только вместо линии получаются каракули. Уже по разному пробовал, шрифты менял и ничего не помогает. Получается или текс по-русски а вместо линии непонятно что, или линия нормальная а вместо текста абракадабра. Как это можно одновременно сделать? #include <iostream> #include <windows.h>... подробнее

Показать сообщение отдельно
shPavel25
6 / 6 / 0
Регистрация: 29.03.2011
Сообщений: 44

Дерево отрезков - C++

30.07.2012, 21:00. Просмотров 2165. Ответов 4
Метки (Все метки)

Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все алгоритмы, процедуры подсчета и т. д.), но сложность состоит в том, что я не понимаю строищихся структур и вообще никогда не программировал на c++.Поэтому прошу помочь собрать все воедино (чтение из файла, работа программы, запись в файл). Основная задача - считать с файла, воспользоваться функцией, вывести в файл

Дан массив целых чисел. Поступают запросы модификации элемента и поиска суммы элементов на отрезке. Необходимо ответить на каждый запрос суммы.
Вход:
В первой строке через пробел записаны два натуральных числа N и M (N, M < 105), где N – количество элементов массива, M – количество запросов. Во второй строке записан массив чисел (элементы массива разделены пробелом). В следующих M строках идут запросы (по одному в строке). Запрос вида 'M 5 9' означает, что необходимо присвоить элементу с индексом 5 число 9. Запрос вида 'S 2 4' означает, что необходимо найти сумму элементов массива, начиная от элемента с индексом
2 и заканчивая элементом с индексом 4 (включая эти два элемента). Гарантируется, что второй индекс больше первого. Гарантируется, что массив имеет элементы с такими индексами. Все элементы в массиве до и после замены – неотрицательные целые числа меньше 10.
Индексация элементов массива идет с нуля.
Выход:
Для каждого запроса поиска суммы выведите результат его выполнения в порядке появления (каждый на отдельной строке)
.***решение

Построим бинарное дерево T следующим образом. Корень дерева будет храниться в элементе T[1]. Он
будет содержать сумму элементов A[0..N-1], т.е. всего массива. Левый сын корня будет храниться в элементе T[2] и содержать сумму первой половины массива A: A[0..N/2], а правый сын - в элементе T[3] и содержать сумму элементов A[N/2+1..N-1]. В общем случае, если T[i]-ый элемент содержит сумму элементов с L-го по R-ый, то его левым сыном будет элемент T[i*2] и содержать сумму A[L..(L+R)/2], а его правым сыном будет T[i*2+1] и содержать сумму A[(L+R)/2+1..R]. Исключение, разумеется, составляют листья дерева - вершины, в которых L = R.

Рассмотрим теперь операцию суммы на некотором отрезке [L; R]. Мы встаём в корень дерева (i=1), и
рекурсивно движемся вниз по этому дереву. Если в какой-то момент оказывается, что L и R совпадают с границами отрезка текущего элемента, то мы просто возвращаем значение текущего элемента T. Иначе, если отрезок [L; R] целиком попадает в отрезок левого или правого сына текущего элемента, то мы рекурсивно вызываем себя из этого сына и найденное значение возвращаем. Наконец, если отрезок [L; R] частично принадлежит и отрезку левого сына, и отрезку правого сына, то делим отрезок [L; R] на два отрезка [L; M] и [M+1; R] так, чтобы первый отрезок целиком принадлежал отрезку левого сына, а второй отрезок - отрезку правого сына, и рекурсивно вызываем себя и от первого, и от второго отрезков, возвращая сумму найденных сумм.
Теперь рассмотрим операцию изменения значения некоторого элемента с индексом K. Будем спускаться по дереву от корня, ища тот лист, который содержит значение элемента A[K]. Когда мы найдём этот элемент, просто изменим соответствующее значение в массиве T и будем подниматься от текущего элемента обратно к корню, пересчитывая текущие значения T. Понятно, что таким образом мы изменим все значения в дереве, которые нужно изменить.
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
vector<long long> t;
int n;
void build (const vector<int> & a, int i = 1, int l = 0, int r = n-1) {
if (i == 1)
t.resize (n*4 + 1);
if (l == r)
t[i] = a[l];
else {
int m = (l + r) / 2;
build (a, i*2, l, m);
build (a, i*2+1, m+1, r);
t[i] = t[i*2] + t[i*2+1];
}
}
long long sum (int l, int r, int i = 1, int tl = 0, int tr = n-1) {
if (l == tl && r == tr)
return t[i];
int m = (tl + tr) / 2;
if (r <= m)
return sum (l, r, i*2, tl, m);
if (l > m)
return sum (l, r, i*2+1, m+1, tr);
return sum (l, m, i*2, tl, m) + sum (m+1, r, i*2+1, m+1, tr);
}
void update (int pos, int newval, int i = 1, int l = 0, int r = n-1) {
if (l == r)
t[i] = newval;
else {
int m = (l + r) / 2;
if (pos <= m)
update (pos, newval, i*2, l, m);
else
update (pos, newval, i*2+1, m+1, r);
t[i] = t[i*2] + t[i*2+1];
}
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru