Обновить массив

Дан массив arr, который инициализируется значением 0, т.е. arr[i]=0, где 0 ‹ i ‹ n

над ним выполняются две операции

  1. обновить к р х

    Обновление делает следующее:

    for(i=k;i<=r;i++)
{
    arr[i]=x;
    x+=x;
}

  2. запрос к р

    Запрос вычисляет следующую сумму:

    for(i=k;i<=r;i++)
{
    sum+=arr[i];
}
print(sum);

Мое решение:
Я думал о грубой силе, но это медленно. Я думал о дереве сегментов, но в дереве сегментов обновление выполняется с постоянной величиной, поэтому оно не работает. Какой может быть хороший алгоритм для решения этой проблемы?

Ограничения

размер массива ‹=10^5

количество операций(обновление,запрос) ‹=10^5


algorithm segment-tree
person nil96    schedule 05.01.2016    source источник
comment
Можете ли вы добавить ограничения проблемы? Например, диапазон значений, которые могут принимать x, k и r.   -  person Aseem Baranwal    schedule 05.01.2016
comment
Используйте дерево Фенвика, чтобы сохранить суммы префиксов.   -  person kfx    schedule 05.01.2016
comment
Размещая такой вопрос, вам нужно показать ограничения, такие как общий размер массива и количество запросов. Часто решение жестко привязано к ограничениям.   -  person Edgar Rokjān    schedule 05.01.2016
comment
Ограничивает размер массива ‹=10^5 число операций (обновление, запрос) ‹=10^5   -  person nil96    schedule 06.01.2016

Ответы (1)


arrow_upward
2
arrow_downward

Вам нужно ленивое распространение в деревьях сегментов. Мы создаем массив lazy[] с таким же размером, как у массива дерева сегментов. Идея состоит в том, что мы можем избежать рекурсивных вызовов в обновлении, отложив их и выполняя эти обновления только тогда, когда это необходимо.

Мой код ниже выполняет обновление и извлечение суммы для предопределенных данных, вы можете возиться с main, чтобы принимать пользовательские данные в желаемом шаблоне и добавлять настройки, такие как x+=x и т. д.

https://ideone.com/kZsJ0E

Я предлагаю вам открыть код и прочитать объяснение ниже, чтобы лучше понять, поскольку ленивое распространение часто трудно понять.

Как это работает:

  • Первоначально все записи в массиве lazy[] установлены равными 0, что означает, что в диапазоне, который представляет этот узел, не осталось никакой оставшейся работы.

  • Чтобы обновить дерево сегментов в индексах массива с qs (начало запроса) до qe (конец запроса):

    -> Если текущий узел дерева сегментов имеет какое-либо ожидающее обновление, мы назначаем этот узел (lazy_value)*(длина интервала, который он представляет) и назначаем ленивые значения для его дочерних элементов как new_value

    -> Если диапазон текущего узла полностью лежит в диапазоне запроса обновления.

    i) Update the Current node, by assigning it (lazy_value)*(length of interval it represents)

ii) Postpone updates to children by setting lazy values for children nodes as new_value

    -> Если диапазон текущего узла перекрывается с диапазоном обновления, следуйте тому же подходу, что и выше, при простом обновлении.

    а. Recur для левых и правых детей.

    б. Обновите текущий узел, используя результаты левых и правых вызовов.

  • Теперь, когда мы используем процедуру get_sum, мы также будем обновлять текущий узел, если у него есть какие-либо ожидающие обновления, и откладывать обновления для дочерних узлов.

В целом, здесь сложно объяснить всю работу ленивого распространения, хотя я надеюсь, что код и объяснение помогут.

Подробнее о ленивом распространении см.

https://www.hackerearth.com/notes/segment-tree-and-lazy-propagation/

person Avikalp Srivastava    schedule 06.01.2016