как мы можем добавить элемент в начало массива в каждой операции и вычислить сумму любого заданного диапазона.?

Question

Сначала вам задан массив из N целых чисел (1<=N<=105). Учитывая этот массив, вы должны выполнить 2 вида операций:

(i) Operation 1 : Op1(l, r) 

Вам дается 2 целых числа l и r. (1 <= l <= r <= current size of the array). Вам нужно вернуть сумму всех элементов с индексами между l и r (оба включительно). То есть, если элементы, находящиеся в настоящее время в массиве, являются a1, a2, a3 .... an, вам необходимо вернуть следующее sum : al + al+1 + al+2 ... + ar.

(ii) Operation 2 : Op2(x) 

Вам предоставляется целое число x (|x| <= 109). Добавьте этот элемент в начало массива. После этой операции x теперь станет a1, old a1 теперь станет a2 и т. Д. Размер массива увеличится на 1.

Я сделал дерево сегментов с начальным заданным массивом и мог вычислять сумму диапазона .... но как я мог добавить один элемент в дереве сегментов и соответствующим образом изменить его?

Answer 1

Для этого типа проблем вы можете использовать Структуру данных, известную как TREAP (Рандомизированное дерево двоичного поиска). Для получения дополнительной информации о декартово дерево следовать этой ссылке - cs.cornell.edu/Courses/cs312/2003sp/lectures/lec26.html

Answer 2

Попробуйте автономный алгоритм: -

Первое чтение в массиве.

Тогда читать во всех запросов и хранить их, а также подсчитать не 2 типа запросов, пусть это будет К.

Теперь создайте новый массив б длины K + длина (а).

Теперь, начиная с индекса 1 в b и перемещая ваши запросы назад, для каждого запроса типа 2 добавьте его элемент в массив b.

Теперь постройте дерево сегментов или двоичное индексированное дерево на массиве b.

Использование переменной с сосчитать ЧИСЛО 2 типа запросов, встретившиеся до сих пор и инициализировать его в 0.

Затем траверс список запросов и для каждого запроса типа 2 просто увеличиваем с на 1.

Для запроса типа 1, имеющего диапазон l ... r в массиве a, его диапазон в массиве b будет соответствовать (l + kc) ... (r + kc).

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