основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Олимпиады >> Задачи

Страницы: 1
juver
здесь был не раз


Рег.: 06/21/06
Сообщений: 29
Из: Челябинск
Дерево отрезков
      #11992 - 08/31/06 04:22 AM

Скажите пожалуйста где можно почитать про деревья отрезков, декартовы деревья кроме лекция Павлова и Метельского. И как в общем называется "дерево максимумов"(у Ивана Метельского)?

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
necro
здесь был не раз


Рег.: 03/28/06
Сообщений: 28
Из: Украина. Киев
Re: Дерево отрезков [Re: juver]
      #11993 - 08/31/06 06:47 AM

Эта тема уже была... Короче шота есть в Препарате и Шамосе, и шота в Кормене

--------------------
To be or not to be = true 8)


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
M_GustokashinМодератор
приобщившийся
****

Рег.: 07/31/04
Сообщений: 51
Из: МГУ ФДС-7, Москва, Россия
Re: Дерево отрезков [Re: necro]
      #11994 - 08/31/06 10:35 AM

Е.В.Андреева (?):
Code:
Глобальные переменные: A – массив чисел с индексами от 1 до N, для которого строим дерево интервалов; RSQ – массив чисел для хранения дерева в памяти.
Процедуры для работы с деревом:
procedure MakeRSQ;
var i:longint;
begin
fillchar(RSQ,sizeof(RSQ),0);
for i:=N to 2*N-1 do
RSQ[i]:=A[i-N+1];
for i:=N-1 downto 1 do
RSQ[i]:=RSQ[2*i]+RSQ[2*i+1]
end;
procedure Replace(i,x:longint);
begin
i:=i+N-1;
RSQ[i]:=x;
while (i div 2>0) do
begin
i:=i div 2;
RSQ[i]:=RSQ[2*i]+RSQ[2*i+1]
end
end;
function GetSum(i,j:longint):longint;
var count:longint;
begin
count:=0;
i:=i+N-1;
j:=j+N-1;
while (i<j) do
begin
if odd(i) then
count:=count+RSQ[i];
if not odd(j) then
count:=count+RSQ[j];
i:=(i+1) div 2;
j:=(j-1) div 2
end;
if i=j then
count:=count+RSQ[i];
GetSum:=count
end;



Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 409 анонимных пользователей просматривают этот форум.

Модератор:  Илья Кантор, Sergeyev, M_Gustokashin 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 10116

Rate this topic

Переход в