Недавно я изучил структуру данных Дерево Фенвика (двоичное индексированное дерево).
При запросе я могу понять, зачем вычитать (idx и -idx). Однако я не могу понять, зачем добавлять (idx и -idx) при обновлении значения.
Другими словами, я знаю, что мы должны обновить все интервалы, на которые повлияет обновление какого-то одного элемента x, и я знаю, что BIT[x] обновляется первым, но не могу понять, почему следующий индекс должен быть обновлен. БИТ [x + (x & -x)]
Спасибо.
Вот хорошее объяснение: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
Ключевая идея состоит в том, что если f(i) — это частота с индексом i, то t(i) — это кумулятивная частота для всех (i — (r — 1)) .. i, где r — наименьший установленный бит в i. Вы можете рассчитать r как r = i & -i.
[EDIT: выше я неправильно написал (r - 1) как (2 ^ r - 1).]
Например, если i = 12 = 1100_2, то r = 100_2 и t(i) = f(1001_2) + f(1010_2) + f(1011_2) + f(1100_2) = f(9) + f(10) + f(11) + f(12).
При вычислении кумулятивной частоты от 0 .. i вы, по существу, суммируете значения t в i, i с удаленным наименьшим установленным битом, i с удаленными наименьшими двумя установленными битами, ... и так далее, пока не закончатся биты.
Например, если i = 12 = 1100_2, нам нужно t(1100_2) + t(1000_2).
Следовательно, если вы измените значение в f(i), вы должны изменить все затронутые значения t. Это t(i), t(i + r), 2t(i + r), 4t(i + r), ... и так далее, пока мы не превысим последний индекс. Именно эти затронутые значения t мы будем исследовать для любого расчета кумулятивной частоты для индекса j >= i.
[EDIT: исправлена последовательность «затронутых значений t» в последнем абзаце в ответ на исправление j_random_hacker.]
