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

@shPavel25 · Регистрация: 29.03.2011

Author24 — интернет-сервис помощи студентам

Добрый день, помогите пож-та решить задачи на с++. Нашел решение (расписаны все алгоритмы, процедуры подсчета и т. д.), но сложность состоит в том, что я не понимаю строищихся структур и вообще никогда не программировал на 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++

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];
}
}

@b_kasenov47 · 31.07.2012, 00:07

Опять списал с емакса... Там дерево отрезков нормально объяснено.

@shPavel25 · 31.07.2012, 00:09 **[ТС]**

я не спорю, все хорошо объяснено, мне не совсем понятно как считывать с файла и закидывать в функцию, какая структура данных должна быть

@b_kasenov47 · 31.07.2012, 00:16

C++

1 2	freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

связывание с файлом. Затем используя потоки cin, cout ввод-вывод. в Дейкстре есть и ввод и вывод. он аналогичен для всех типов данных. Структура данных написана уже (массив, хранящий двоичное дерево)

@shPavel25 · 31.07.2012, 01:23 **[ТС]**

то есть если напишу так:

C++

#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]<<'" ";
}

или я не правильно понял?

@b_kasenov47 14 / 14 / 3 Регистрация: 28.07.2012 Сообщений: 57
	31.07.2012, 00:07	2
	Опять списал с емакса... Там дерево отрезков нормально объяснено. 0

@shPavel25 6 / 6 / 0 Регистрация: 29.03.2011 Сообщений: 47
	31.07.2012, 00:09 [ТС]	3
	я не спорю, все хорошо объяснено, мне не совсем понятно как считывать с файла и закидывать в функцию, какая структура данных должна быть 0

	31.07.2012, 01:23