Как узнать, какая позиция имеет префикс M в BIT?

Question

Предположим, я создал двоичное индексированное дерево с префиксной суммой длины N. Основной массив содержит только 0с и 1s. Теперь я хочу найти, какой индекс имеет префиксную сумму M(это означает, что точно M 1с).

Как мой массив a[]={1,0,0,1,1};

Префикс-сумма будет выглядеть {1,1,1,2,3};

теперь третий индекс (на основе 0) имеет префиксную сумму 2.

Как я могу найти этот индекс с помощью BIT?

Заранее спасибо.

Answer 1

Почему вы не можете выполнить бинарный поиск по этому индексу? Это займет O(log n * log n) время. Вот простая реализация -

int findIndex(int sum) {
    int l = 1, r = n;
    while(l <= r) {
        int mid = l + r >> 1;
        int This = read(mid);
        if(This == sum) return mid; 
        else if(This < sum) l = mid+1; 
        else r = mid-1;
    } return -1;
} 

Я использовал read(x) функция. Это должно вернуть сумму интервала [1,x] в O(log n) время. Общая сложность будет O(log^2 n),
Надеюсь, поможет.

Answer 2

Если элементы в массиве a[n] неотрицательный (и префиксный массив сумм p[n]является неубывающим), вы можете найти элемент по префиксной сумме как префиксную сумму запроса по индексу из BIT, что занимает O(logn) время. Единственное отличие состоит в том, что вам нужно сравнить сумму префикса, которую вы получаете на каждом уровне, с вашим входом, чтобы решить, какое поддерево вам нужно искать впоследствии - если сумма префикса меньше, чем ваш ввод, продолжайте поиск в левом поддереве; в противном случае ищите правильное поддерево; повторяйте этот процесс до тех пор, пока не достигнете узла, который суммирует желаемую сумму префикса, и в этом случае возвращает индекс узла. Идея аналогична бинарному поиску, потому что суммы префиксов естественным образом сортируются в BIT. Если есть отрицательные значения в a[n]этот метод не будет работать, так как суммы префиксов в BIT не будут сортироваться в этом случае.