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

Декартово дерево. Множественные операции
Автор I_love_Evgenia, 12 лет назад, По-русски

Прочитал данную статью, вроде бы понял, решил на практике опробовать. Написал следующую реализацию для суммы и прибавления константы, но видимо я что-то неправильно понимаю, в частности, после прибавления считает неправильно. В чем ошибка?

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

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

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

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

    Там по неявному ключу реализация, а я хочу пока по явному понять

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

Было бы проще помочь, если бы была ссылка на условие задачи... А так, не совсем понятно что требуется в задаче, а что Вы пытаетесь сделать...

Вот например sum(a, b) это сумма для ключей [a, b) [a, b + 1] если я правильно понял, именно так реализовано. Или все-таки нужно [a, b]?

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

    насколько я понял, человек просто хочет реализовать то что прочитал, закрепить на практике

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

В процедуре push помимо пересчёта для детей следует обновлять ключ текущего элемента. А вообще порядок дебага всяких структур данных примерно такой: просто выводить все элементы на экран после каждой операции. И ручками смотреть, что не так.

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

    Также еще совет по реализации: избавляйтесь от избыточного кода: в merge можно все строчки push(...) заменить на push(l); push(r); в начале процедуры — push у Вас нормально работает и тогда, когда передают ноль.

    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Ошибка была в том, что надо было сразу писать по неявному, проще и работает

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

    А чем там оно особо отличается в написании? :/

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

      Да особо ничем) Видимо отсутствие ключа компенсирует кривость рук.

      → Ответить