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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.63
shPavel25
6 / 6 / 0
Регистрация: 29.03.2011
Сообщений: 44
#1

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

30.07.2012, 21:00. Просмотров 2341. Ответов 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];
}
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.07.2012, 21:00
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Дерево отрезков (C++):

Медленное дерево отрезков - C++
Приветствую. Пишу дерево отрезков для задачи нахождения сумм на отрезках. Оно работает, даже вроде правильно, но при массиве 105 и...

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

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

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

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

Есть ли у кого похожий алгоритм: распределения отрезков разной длины внутри отрезков фиксированной длины? - C++
Народ помогите мне с программой распределения отрезков разной длины внутри отрезков фиксированной длины с минимальными остатками. К...

4
b_kasenov47
14 / 14 / 1
Регистрация: 28.07.2012
Сообщений: 57
31.07.2012, 00:07 #2
Опять списал с емакса... Там дерево отрезков нормально объяснено.
0
shPavel25
6 / 6 / 0
Регистрация: 29.03.2011
Сообщений: 44
31.07.2012, 00:09  [ТС] #3
я не спорю, все хорошо объяснено, мне не совсем понятно как считывать с файла и закидывать в функцию, какая структура данных должна быть
0
b_kasenov47
14 / 14 / 1
Регистрация: 28.07.2012
Сообщений: 57
31.07.2012, 00:16 #4
C++
1
2
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
связывание с файлом. Затем используя потоки cin, cout ввод-вывод. в Дейкстре есть и ввод и вывод. он аналогичен для всех типов данных. Структура данных написана уже (массив, хранящий двоичное дерево)
0
shPavel25
6 / 6 / 0
Регистрация: 29.03.2011
Сообщений: 44
31.07.2012, 01:23  [ТС] #5
то есть если напишу так:

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
 
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];
}
}
int main()
{
    freopen("input.txt","r",stdin); 
    freopen("output.txt","w",stdout);
int n,m;
cin>>n>>m;
 vector<int> a(n);
  for (int i = 0; i <n; i++)
         cin>>a[i];
//я так понимаю теперь строим T
build (a);
//по задаче подается m запросов - если S 2 4  - сумма со 2 по 4 элемента включительно
// М 5 9  - необходимо присвоить элементу 5 значение 9
char operation;
int q1,q2;
for (i=0; i<m; ++i)
{
cin>>operation>>q1>>q2;
if (operation="S") 
sum(q1,q2);
else 
update(q1,q2);
}
for (i=0; i<m; ++i)
cout<<t[i]<<'" ";
}
или я не правильно понял?
0
31.07.2012, 01:23
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.07.2012, 01:23
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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