2955. Персистентный массив

Дан массив (вернее, первая, начальная его версия). Нужно уметь отвечать на два запроса:

a_i[j] = x – создать из i-ой версии новую, в которой j-ый элемент равен x, а остальные элементы такие же, как в i-ой версии.

get a_i[j] – сказать, чему равен j-ый элемент в i-ой версии.

Вход. Количество чисел в массиве n (1 ≤ n ≤ 10⁵) и n элементов массива. Далее количество запросов m (1 ≤ m ≤ 10⁵) и m запросов. Формат описания запросов можно посмотреть в примере. Если уже существует k версий, новая версия получает номер k + 1. И исходные, и новые элементы массива – целые числа от 0 до 10⁹. Элементы в массиве нумеруются числами от 1 до n.

Выход. На каждый запрос типа get вывести соответствующий элемент нужного массива.

Пример входа	Пример выхода
6 1 2 3 4 5 6 11 create 1 6 10 create 2 5 8 create 1 5 30 get 1 6 get 1 5 get 2 6 get 2 5 get 3 6 get 3 5 get 4 6 get 4 5	6 5 10 5 10 8 6 30

РЕШЕНИЕ

структуры данных – персистентное дерево отрезков

Анализ алгоритма

Элементы каждой копии массива будем хранить в листах дерева отрезков. В вершинах, не являющимися листами, хранить ничего не будем. Например массив, заданный в условии, будет храниться в следующей структуре:

Копии массивов храним в массиве деревьев отрезков PSTree. Инициализация новой (например первой) копии из нулевой происходит следующим образом: создадим новую вершину w, в которую скопируем содержимое вершины, на которую указывает PSTree[0].

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

Реализация алгоритма

Объявим массив деревьев отрезков PSTree. Деревья отрезков строим на указателях.

#define MAX 100010

struct SegmentTree

{

int value;

struct SegmentTree *Left, *Right;

} *PSTree[MAX];

Создание дерева отрезков V из элементов a[L..R].

void build(SegmentTree &V, int *a, int L, int R)

{

if (L == R)

{

V.value = a[L];

V.Left = V.Right = NULL;

return;

}

int Mid = (L + R) / 2;

V.Left = new SegmentTree(); build(*V.Left,a,L,Mid);

V.Right = new SegmentTree(); build(*V.Right,a,Mid+1,R);

}

В дереве отрезков V совершим изменение a[pos] = value.

void Update(SegmentTree &V, int L, int R, int pos, int value)

{

if (L == R)

{

V.value = value;

return;

}

int Mid = (L + R) / 2;

if (pos <= Mid)

{

SegmentTree *Left = new SegmentTree();

*Left = *V.Left;

V.Left = Left;

Update(*Left, L, Mid, pos, value);

}

else

{

SegmentTree *Right = new SegmentTree();

*Right = *V.Right;

V.Right = Right;

Update(*Right, Mid+1, R, pos, value);

}

}

В дереве отрезков V возвратим значение a[pos].

int Get(SegmentTree &V, int L, int R, int pos)

{

if (L == R) return V.value;

int Mid = (L + R) / 2;

if (pos <= Mid)

return Get(*V.Left,L,Mid,pos);

else

return Get(*V.Right,Mid+1,R,pos);

}

Основная часть программы. Читаем входные данные.

scanf("%d",&n);

for(i = 1; i <= n; i++) scanf("%d",&a[i]);

Сохраняем входной массив в виде дерева отрезков в PSTree[0].

PSTree[0] = new SegmentTree();

build(*PSTree[0],a,0,n);

Последовательно обрабатываем m запросов.

scanf("%d",&m); ptr = 1;

while(m--)

{

scanf("%s",q);

if (q[0] == 'c')

{

Обработка операции create.

scanf("%d %d %d",&ver,&pos,&value);

SegmentTree *node = new SegmentTree();

*node = *PSTree[ver-1];

PSTree[ptr] = node;

Update(*PSTree[ptr++],0,n,pos,value);

}

else

{

Обработка операции get.

scanf("%d %d %d",&ver,&pos);

printf("%d\n",Get(*PSTree[ver-1],0,n,pos));

}

}