Pull to refresh

Comments 9

«Статья написана для тех, кто знает, что такое дерево Фенвика и описывает его модификацию для максимума.»

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

  • Зачем нам нужен старший бит в числе? Можно же просто делать цикл до размера массива/нуля. Обычный Фенвик прекрасно работает на массивах произвольного размера
  • Дерево Фенвика по-английски пишется как Fenwick tree
  • Разве нельзя сделать инициализацию за линию? Дополнило бы
  • Статья была бы лучше, если бы провелось хоть какое-то сравнение с, например, деревом отрезков и sparse table по времени — инициализация, изменение, запрос
  • И мне непонятно, чем такая реализация лучше дерева отрезков, которое занимает меньше места (обновление — один for, две строки; запрос — один while, два if, шесть строчек) и интуитивнее понятнее.
Правописание исправил, спасибо указание.
Про сравнение со ST и дерево отрезков — это есть в статье, на которую я ссылаюсь.
Про реализацию. Хм, Вы первый человек от которого я слышу, что дерево отрезков проще.Мнение большинства, вроде бы, ровно наоборот.=) Да, оно может быть, чуть-чуть понятнее, но и фенвик не сложный.
Инициализация за линию? что-то мне не приходит пока в голову, как
Про старший бит — мы же идем с двух концов, и нам надо точно знать как они пересекутся
Интересна именно данная реализация — она существенно отличается, например, наличием нескольких массивов и, соответственно, большими прыжками по памяти.

Нет, имеется введу, что моё дерево отрезков проще Вашего кода, а мой Фенвик для суммы, в свою очередь, проще дерева отрезков (одному for'у из одной команды на каждую операцию).

Не вникал, но хочется сказать, что «детьми вершины» являются только те, которые располагаются левее/правее (в зависимости от массива). Просто надо перебрать вершины в нужном порядке и релаксировать только из текущей вершины. Можете думать об этом, как о динамике.

Понял. Верно ли, что получается что-то в стиле sparse? Еще совет по улучшению: выложить хоть что-то, кроме кода. Например, фразу «в одном массиве будет то-то, в другом — то-то, когда приходит запрос, мы разбиваем его на два почти всегда пересекающихся размером 2^k»
Что может быть проще пары while'ов? Если же сравнивать длину кода, то я за этим не гнался.Задача была написать понятный код, который говорит сам за себя. Поэтому кроме кода мало чего есть. Думается мне, что человек, знакомый с деревом Фенвика, легко поймет и эту его модификацию.

Про инициализацию — все равно пока не думаю, что так возможно.
Нет, на sparse это не сильно похоже.Ну только с очень-очень большой долей абстракции.
Only those users with full accounts are able to leave comments. Log in, please.