Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/19: Рейтинг темы: голосов - 19, средняя оценка - 5.00
6 / 6 / 0
Регистрация: 29.03.2011
Сообщений: 47
1

Дерево отрезков

30.07.2012, 21:00. Просмотров 3615. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.07.2012, 21:00
Ответы с готовыми решениями:

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

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

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

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

4
14 / 14 / 3
Регистрация: 28.07.2012
Сообщений: 57
31.07.2012, 00:07 2
Опять списал с емакса... Там дерево отрезков нормально объяснено.
0
6 / 6 / 0
Регистрация: 29.03.2011
Сообщений: 47
31.07.2012, 00:09  [ТС] 3
я не спорю, все хорошо объяснено, мне не совсем понятно как считывать с файла и закидывать в функцию, какая структура данных должна быть
0
14 / 14 / 3
Регистрация: 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
6 / 6 / 0
Регистрация: 29.03.2011
Сообщений: 47
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
31.07.2012, 01:23

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

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

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

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


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

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

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