Сравнение сложности операций двоичного индексированного дерева с обычным подходом

Question

Я просматривал эту статью, чтобы понять BIT: https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/#c217533

Здесь автор говорит следующее в одном месте:

Если мы посмотрите на операцию for l oop в update (), мы увидим, что l oop выполняет максимальное количество битов в индексе x, которое ограничено, чтобы быть меньше или равным n (размер данного массива ), поэтому мы можем сказать, что операция обновления занимает не более O (log2 (n)) времени

Тогда мой вопрос в том, может ли она go до n (размер данного array), то чем временная сложность отличается от обычного подхода, который он упомянул в начале, потому что в этом обновлении должно быть O (1)? и prefixsum (int k) может go до максимального числа

Answer 1

Ключ в том, что вы делаете не шаг 1 в l oop, а шаг размером x&-x. Это эквивалентно движению вверх по дереву к следующему соответствующему узлу, который должен включать текущий, и, таким образом, дает вам наихудший случай O(log n).