Шаг обновления в Fenwick Trees

Question

Мой вопрос касается полного обоснования шага обновления в Binary Indexed Trees (деревья Фенвика). Таким образом, при обновлении нашего массива с определенным приращением в определенной позиции обновление происходит следующим образом:

void updateBIT(int BITree[], int n, int index, int val)
{
    // index in BITree[] is 1 more than the index in arr[]
    index = index + 1;

    // Traverse all ancestors and add 'val'
    while (index <= n)
    {
       // Add 'val' to current node of BI Tree
       BITree[index] += val;

       // Update index to that of parent in update View
       index += index & (-index);
    }

Моя проблема с index += index & (-index); часть. Обратите внимание, что я понимаю index & (-index) немного, особенно в контексте запроса дерева.

Я попробовал несколько примеров вручную, используя это правило обновления индекса, но мне не удалось найти логику добавления index & (-index) для того, чтобы перейти к следующему узлу, который должен быть обновлен.

От того, что я получил до этого момента, узел i в BIT "отвечает" за исходные значения в массиве, начиная от [i - i & (-i) + 1, i], так что это подразумевает, что любой узел попадет в диапазон этой формы. Конкретно, насколько я понимаю, при желании обновить позицию k в исходном массиве мы выполняем следующие шаги (концептуально, а не в реальном коде):

• итерация 0: Обновить BIT[k + 1] (индексы сдвинуты на 1 в массиве BIT). Пока еще на итерации 0мы обновляем индекс, на который мы смотрим, поэтому я предполагаю, что мы ищем следующий наименьший интервал, который отвечает за узел kследовательно, нам нужно найти следующий индекс i где i - i & (-i) < k < i, Найти этот индекс i увеличивая текущий индекс на k & (-k),

Остальные итерации происходят таким же образом, пока мы не выйдем за пределы. Я пробовал множество примеров вручную, и до сих пор не понимаю, зачем добавлять i & (-i) ведет нас к следующему правильному узлу. Каждый и каждый учебник, который я нашел в Интернете, включая видео, абсолютно неуместен в этом вопросе.

Здесь есть несколько связанных вопросов о битах, пожалуйста, не объединяйте их с моими, прежде чем читать их внимательно. Насколько мне известно, этот конкретный вопрос не получил ответа.

Answer 1

Итак, позвольте мне попытаться объяснить вышеприведенный сценарий на простом примере.

Давайте принимать i = 12, Теперь мы обновляем BIT[12], Теперь следующий шаг в соответствии с алгоритмом обновления i += i&(-i),

Что такое 12 в двоичном = 01100, Последний установленный бит 2, значение 2^2 = 4 (как вы знаете

0th bit value is 2^0 = 1
1st bit value is 2^1 = 2
2nd bit value is 2^2 = 4.

Аналогичным образом для других битов.

Так что теперь следующий индекс, который мы будем обновлять, 12 + 4 = 16, т.е. BIT[16],

Теперь речь шла о том, как работает система. Позвольте мне объяснить простыми словами, почему эта техника работает.

Скажем, мне нужно обновить index = 1 и скажем, значение массива MAX равно 8. Так что весь индекс я буду обновлять 1,2,4,8,

Теперь, скажем, мне нужно обновить index = 3, Таким образом, индексы массива я буду обновлять 3,4,8,

Итак, вы видите, как до сих пор BIT[4] получил сумму всех значений из индекса массива 1 to 4,

Теперь предположим, что вам нужно получить общую сумму за первые 4 числа, просто BIT[4] и вы пройдете через индексы 4,0, Короче говоря, вы не проходите через 1,2,3, Как мы видели, как эти индексы были покрыты из-за битовых манипуляций.

Надеюсь это поможет!