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

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

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

Соответственно, встали такие вопросы:

1) возможно ли такое вообще?

2) если да, пользуется ли кто-то этим или предпочитают альтернативы?

3) есть ли статьи/примеры/видео/что-либо на эту тему?

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

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

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

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

    Да нужно что-то типа такого, только на прямоугольнике :)

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

      А чем это отличается от того, что я сказал? Возможно, я чего-то не понимаю.

      http://e-maxx.ru/algo/fenwick_tree — там глава о двумерном случае, если что.

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

        Ну как же, чем, в статье групповые модификации, а здесь единичные.

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

          А, ну тогда нельзя наверно=)

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

            Есть подозрения, что можно :) но моих фиолетовых мозгов чет не хватает, чтобы придумать, как это сделать :)

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

            Да 146% можно. Может быть, к вечеру подумаю о том, как именно...

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

      Примерно так же и делается. Только функцию надо хранить не совсем линейную, а вот такого вида: f(x, y) = ax + by + cxy + d.

      Сначала превратили запросы на прямоугольниках в запросы на углах, растущих влево-вверх (формула включений-исключений). Говорим, что у нас запрос "сумма на угле" к двумерному Фенвику таких функций должен выдать некоторую функцию, подставив в которую координаты этого же угла должен получиться корректный ответ.

      Запрос изменения на прямоугольнике аналогичны превратили в четыре запроса на углах, растущих вправо-вниз. Изменение каждого угла — это просто добавить в его вершину функцию вида f(x, y) = (x - x0 + 1)(y - y0 + 1).

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

        спасибо за ответ! :) Но осмысление пока идет очень тяжело :))

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

Вот в этой работе что-то такое описывается.

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

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