Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Алгоритм поиска суммы элем. массива в огр. отрезке

Автор: baye 26.1.2007, 21:25

Помогите найти алгоритм RSQ! Я вроде реализовал, но не уверен! smile

Автор: MBo 27.1.2007, 12:41

Что такое - алгоритм RSQ??
Да и тему надо бы расшифровать...

Автор: esperant0 27.1.2007, 16:58

просто проссумируйте все
элементы от Л до Р.

Автор: SoWa 28.1.2007, 21:47

Да, иначе никак. Если конечно массив- не прогрессия

Автор: comp 28.1.2007, 22:29

Ну почему иначе ни как... есть же такая структура данных как дерево фенвика... там всё это делается ну на порядок быстрее...

Автор: SoWa 29.1.2007, 08:49

Расскажи поподробнее?

Автор: baye 29.1.2007, 09:56

COMP был прав. Там точно используется дерево Фенвика. Как его можно реализовать?

Автор: esperant0 29.1.2007, 10:57

Там используется дерево Фенкина.

Хорошо не огород Шматко используется. Может вы все таки сформулируете условие?

Или предоставите участникам форума гадать на кофейной гуще?

Автор: Strannik 29.1.2007, 11:19

Цитата

Там используется дерево Фенкина.

Comp, я конечно понимаю что приятно говорить много умных слов и казаться умнее других. Однако в дальнейшем пожалуйста при использовании необщеизвестных структур, алгоритмов, методов разъясняйте их смысл, или хотя-бы давайте ссылку где можно про них почитать. Иначе теряется смысл форума.

П.С. Без обид, это не замечание, это совет.

Автор: Michael_Rybak 29.1.2007, 22:19

http://byoi.narod.ru/lecture.doc

Сумматор - это и есть RSQ. Вообще статью очень рекомендую.

Автор: comp 29.1.2007, 23:48

+ ещё лекции Павлова... http://slil.ru/23840518 . Также - рекомендую.

Автор: comp 30.1.2007, 20:49

+ пара задачь в тему... что сумел разрыть...
http://acm.timus.ru/problem.aspx?space=1&num=1028
http://acm.timus.ru/problem.aspx?space=1&num=1330

Автор: Silent 4.2.2007, 20:02

Не знаю, как это называется, но проблема решается очень просто.
суммируем элементы массива и искомая сумма вычисляется путем вычитания из элемента по индексу r элемента по индексу l-1:

Код


int a[100];
//здесь должна быть инициализация массива, например for (int i=0;i<100) a[i] = i*i%17;
for (int i=1;i<100;i++) a[i] += a[i-1];
sum=a[r]-a[l-1];

Автор: Michael_Rybak 5.2.2007, 15:00

Запросы по сумме могут чередоваться с запросами на изменение элемента массива.

Автор: ivan219 9.2.2007, 21:35

Код


var
    I: Integer;
    Ar: Array[0..10] of Integer=(...);
    A: Integer;
.
.
for I:=0 to 10 do Inc(A,Ar[I]);
.
.