Comments 9
«Статья написана для тех, кто знает, что такое дерево Фенвика и описывает его модификацию для максимума.»
Вряд ли это надо рассказывать тем, кто знает, что такое дерево Фенвика, т.к. дерево Фенвика для максимума тривиально.
Вряд ли это надо рассказывать тем, кто знает, что такое дерево Фенвика, т.к. дерево Фенвика для максимума тривиально.
писал это потому что в статье на хабре, на которую идет ссылка в начале ничего не говорит про максимум, а в комментариях к ней некоторые люди утверждают, что для максимума написать невозможно. и в некоторых других источниках видел, что отрицается возможность для максимума
Я бы сказал, что оно тривиально для максимума на префиксе/суффиксе, а не на отрезке. Реализации для отрезка я никогда не встречал и ни от кого не слышал.
Несколько мыслей по этому поводу:
- Зачем нам нужен старший бит в числе? Можно же просто делать цикл до размера массива/нуля. Обычный Фенвик прекрасно работает на массивах произвольного размера
- Дерево Фенвика по-английски пишется как Fenwick tree
- Разве нельзя сделать инициализацию за линию? Дополнило бы
- Статья была бы лучше, если бы провелось хоть какое-то сравнение с, например, деревом отрезков и sparse table по времени — инициализация, изменение, запрос
- И мне непонятно, чем такая реализация лучше дерева отрезков, которое занимает меньше места (обновление — один for, две строки; запрос — один while, два if, шесть строчек) и интуитивнее понятнее.
Правописание исправил, спасибо указание.
Про сравнение со ST и дерево отрезков — это есть в статье, на которую я ссылаюсь.
Про реализацию. Хм, Вы первый человек от которого я слышу, что дерево отрезков проще.Мнение большинства, вроде бы, ровно наоборот.=) Да, оно может быть, чуть-чуть понятнее, но и фенвик не сложный.
Инициализация за линию? что-то мне не приходит пока в голову, как
Про старший бит — мы же идем с двух концов, и нам надо точно знать как они пересекутся
Про сравнение со ST и дерево отрезков — это есть в статье, на которую я ссылаюсь.
Про реализацию. Хм, Вы первый человек от которого я слышу, что дерево отрезков проще.Мнение большинства, вроде бы, ровно наоборот.=) Да, оно может быть, чуть-чуть понятнее, но и фенвик не сложный.
Инициализация за линию? что-то мне не приходит пока в голову, как
Про старший бит — мы же идем с двух концов, и нам надо точно знать как они пересекутся
Интересна именно данная реализация — она существенно отличается, например, наличием нескольких массивов и, соответственно, большими прыжками по памяти.
Нет, имеется введу, что моё дерево отрезков проще Вашего кода, а мой Фенвик для суммы, в свою очередь, проще дерева отрезков (одному for'у из одной команды на каждую операцию).
Не вникал, но хочется сказать, что «детьми вершины» являются только те, которые располагаются левее/правее (в зависимости от массива). Просто надо перебрать вершины в нужном порядке и релаксировать только из текущей вершины. Можете думать об этом, как о динамике.
Понял. Верно ли, что получается что-то в стиле sparse? Еще совет по улучшению: выложить хоть что-то, кроме кода. Например, фразу «в одном массиве будет то-то, в другом — то-то, когда приходит запрос, мы разбиваем его на два почти всегда пересекающихся размером 2^k»
Нет, имеется введу, что моё дерево отрезков проще Вашего кода, а мой Фенвик для суммы, в свою очередь, проще дерева отрезков (одному for'у из одной команды на каждую операцию).
Не вникал, но хочется сказать, что «детьми вершины» являются только те, которые располагаются левее/правее (в зависимости от массива). Просто надо перебрать вершины в нужном порядке и релаксировать только из текущей вершины. Можете думать об этом, как о динамике.
Понял. Верно ли, что получается что-то в стиле sparse? Еще совет по улучшению: выложить хоть что-то, кроме кода. Например, фразу «в одном массиве будет то-то, в другом — то-то, когда приходит запрос, мы разбиваем его на два почти всегда пересекающихся размером 2^k»
Что может быть проще пары while'ов? Если же сравнивать длину кода, то я за этим не гнался.Задача была написать понятный код, который говорит сам за себя. Поэтому кроме кода мало чего есть. Думается мне, что человек, знакомый с деревом Фенвика, легко поймет и эту его модификацию.
Про инициализацию — все равно пока не думаю, что так возможно.
Нет, на sparse это не сильно похоже.Ну только с очень-очень большой долей абстракции.
Про инициализацию — все равно пока не думаю, что так возможно.
Нет, на sparse это не сильно похоже.Ну только с очень-очень большой долей абстракции.
Sign up to leave a comment.
Дерево Фенвика для максимума