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

Задачка из 2013-2014 СПбГУ В 6 Дерево Фенвика
Автор Corvo, 11 лет назад, По-русски

Здравствуйте,

Возникла проблема при решении задачи из тренировки 2013-2014 СПбГУ В 6 Дерево Фенвика, В("Звёзды"). Коды закрыты, но может кто-нибудь помочь с идеей решения? Я пробовал вот так, но это неправильно. Ведь необходимо реализовать трехмерное дерево?

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

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

Дерево Фенвика, в вашем случае, отвечает на запрос суммы на прямоугольном параллелепипеде с начальной точкой (0, 0, 0). Подумайте как с помощью таких запросов научиться отвечать на запрос суммы в произвольном прямоугольном параллелепипеде. Рекомендую сначала разобраться, как решать такую задачу в двумерном случае.

Hint: Вам поможет формула включений-исключений.

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

    Можете объяснить, как здесь почему используется формула включений-исключений? В двумерном случае можно и без нее обойтись, а здесь как ?

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

      Может я чего-то глобально не понимаю, но как Вы это делаете в двумерном случае без использования чего-то похожего на формулу включения-исключения?

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

        По моему , та формула намного легче , и до нее можно додуматься самому.А вот в трехмерном случае...

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

          Суть остается той же. При подсчете суммы Вы некоторые элементы считаете дважды, трижды и так далее... Чтобы все правильно учесть, просто применим формулу включений-исключений и получим ответ. И хорошо понимать, что в том, что Вы хотите получить будут присутствовать такие слагаемые вида sum(XX, YY, ZZ), где XX может быть x1 - 1 или x2, YY — y1 - 1 или y2 и ZZ — z1 - 1 или z2. То есть всего 8 штук. Осталось всего лишь найти коэффициенты.

          → Ответить