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

Автор mathAway, история, 4 года назад, По-русски

Задача: есть дерево, в каждой вершине которого записано число. Требуется отвечать на запросы (u,v,k) — найти k-ю порядковкую статистику на пути между вершинами u и v. Количество вершин и количество запросов <= 1e5.Оригинал

Пока что не знаю, как решать эту задачу, но решал похожую: отвечать на запросы (u,k) — найти k-ю порядковую статистику в поддереве вершины u(Оригинал). Там я перенумеровал все вершины таким образом, что задача свелась к нахождению порядковой статистики на отрезке массива, что решается персистентным деревом отрезков. Тут же я не нашёл способа, что и как можно перенумеровать, чтобы достичь подобного эффекта.

Есть идеи?

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

С помощью heavy-light декомпозиции задача сводится к "найти k-ю порядковую статистику в массиве на объединении log n отрезков". Это решается так же, как и обычная k-я порядковая статистика, только теперь вместо параллельного запуска из двух вершин, запускаемся из 2 * "кол-во отрезков, на которые разбился путь" вершин.

UPD. И правда, снизу предложено решение куда лучше

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

    Окей, прочитаю что за она, на это ещё нужно время. Спасибо!

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

    Зачем тут HLD? Можно в персистентном ДО хранить все числа на пути от корня до вершины, для вершины $$$i$$$ обозначим такое дерево как $$$tree_i$$$.

    Тогда ответ считается как спуск по $$$tree_v + tree_u - 2 \cdot tree_{lca(v, u)} + number\,in\,vertex\,lca(v, u)$$$.

    Код очень похож на подсчет на отрезке, где за $$$tree_i$$$ мы обозначаем дерево со всеми числами на префиксе длины $$$i$$$, и спуск происходит по $$$tree_r - tree_{l - 1}$$$.

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

      Блин, а я ведь мыслил очень близко! Но если мы для каждой вершины будем хранить все числа на пути от корня до неё, то не будет ли такое решение потреблять n^2 памяти? Если сравнивать с использованием пдо для нахождения к-й порядковой статистики на отрезке, то там мы строим его так: создаём массив x размера количества различных элементов в исходном массиве, а затем бежим слева направо по этому исходному массиву и прибавляем единичку в соответствующей позиции массива x, только этот массив хранится в виде до и у нас есть все его версии, т.е. пдо. Почему объём памяти куда меньше, чем мне кажется? Если брать, к примеру случай дерева, как последовательно связанных вершин, а корнем является вершина 1.

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

        Это будет $$$O(n \log n)$$$ памяти.

        Пишется аналогично задаче на массиве, просто вместо $$$tree_i = add(tree_{i - 1}, a_i)$$$ (тут $$$a_i$$$ — элемент массива) получается $$$tree_i = add(tree_{parent_i}, a_i)$$$ (тут $$$a_i$$$ — число в вершине, $$$parent_i$$$ — предок в дереве)

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

          Всё, я наконец понял, спасибо :) Я на некоторое время забыл, что обновление в пдо добавляет лишь логарифм вершин.

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

Автокомментарий: текст был обновлен пользователем mathAway (предыдущая версия, новая версия, сравнить).