Блог пользователя KonanMentor

Автор KonanMentor, 10 лет назад, По-русски

Есть массив чисел. Как быстро отвечать на запросы

  • прибавить число на отрезке
  • узнать сколько раз число встречается на отрезке?

Пока что ничего быстрее не придумал.

Если кому интересно, идея sqrt-декомпозиции:

  • разобьем массив на блоков
  • для каждого блока будем хранить
    • cnt[x] — количество чисел x в блоке
    • delta — число, которое надо прибавить ко всем числам в этом блоке

Тогда на запрос прибавления числа D на отрезке будем отвечать так:

  • Если блок полностью входит в отрезок, то изменим его delta на D
  • Иначе пройдемся по элементам, которые лежат в границах запроса, и просто добавим к ним D

    cnt[a[i]] --;
    a[i] += D;
    cnt[a[i]] ++;
    

Запрос о количестве чисел X на отрезке:

  • Если блок полностью входит в отрезок, просто вернем cnt[X - delta]
  • Среди остальных элементов учтем те, которые равны X - delta
  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится -26 Проголосовать: не нравится

За O(log2(n)) вроде можно. Будем поддерживать дерево отрезков, в котором будем хранить количество каждого числа, которое входит в отрезок в мэпе и значение delta. Ответ находить ровно так же, как при корневой декомпозиции для полных блоков. Запрос на добавление — просто в дереве отрезков для нужных вершин увеличиваем delta.
p.s. не прочитал в тэгах, что ты хотел log(n) на запрос)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Не обязательно O(log(n)), хотя бы что-нибудь быстрее корня (:

    Как тогда мержить сыновей вершины с разными delta? Например, такие запросы:

    • добавить 1 на первой половине
    • добавить 2 на второй половине
    • запрос на всем массиве

    По идее, нужно взять ответ из корня, не спускаясь вниз. Как это сделать?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится -15 Проголосовать: не нравится

      Я попытался на скорую руку написать структурку. Вот что получилось.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Так у вас update работает за O(количества чисел в поддереве), так что inc будет работать как минимум за O(длина интервала).

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится

          Да, действительно. Был неправ.

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится -17 Проголосовать: не нравится

            Ну круто, всегда удивлялся среднестатистическому пользователю кодфорс. Не раз встречал комментарии, неуместные по тем, или иным причинам. В этот раз автором этого комментария стал я. Этот пост(как и мой комментарий) прочитало не мало человек, из них почти все подумали что-то типа : "комментатор рак, дебил, поставлю ему минус(от которого никому лучше не станет), он его заслужил" и лишь один(!), спасибо ilyakor, объяснил, в чем моя ошибка. Супер. Класс.

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Ой, все.

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              тут очень странно людей заминусовывают ) не удивлюсь если и с твоим новым комментарием так же поступят, их уже не остановить =)

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

Делаем дерево интервалов, у которого в вершинах лежат Rope'ы, умеющие отвечать на запрос "сколько в тебе чисел x" и прибавлять константу ко всему Rope'у. Запросы делаются тривиально, а вот обновления довольно хитрые. В процессе обновления надо раз cmerge'ить левый и правый Rope'ы в каких-то вершинках. Копировать мы их при этом не хотим (т.к. это долго), а хотим merge'ить за log n без копирования. Это можно сделать, если у нас есть персистентность.

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Жесть с:

    Ладно, если что, буду писать корневую (:

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    А разве мы должны merge'ить ? Мы же не хотим просто приписать в конец одного массива другой. По-моему, нам придется их объединять. А объединение это медленная операция. Если использовать не Rope а Декартово дерево, то будет выполняется за M log(N/M).

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

      Ну да, нужен не Rope, а обычное декартово дерево. И объединение будет тормозить. Значит, так просто не сделаешь, жаль :(