Предположим, я создал двоичное индексированное дерево с суммой префиксов длины N. Основной массив содержит только 0s и 1s. Теперь я хочу найти, какой индекс имеет префиксную сумму M (это означает, что он имеет ровно M 1s).
Как мой массив a[]={1,0,0,1,1};
префикс-сумма будет выглядеть как {1,1,1,2,3};
теперь 3-й индекс (на основе 0) имеет сумму префикса 2.
Как я могу найти этот индекс с помощью BIT?
Заранее спасибо.
Почему вы не можете выполнить бинарный поиск по этому индексу? Это займет 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).
Надеюсь, это поможет.
Если элементы в массиве a[n] неотрицательны (а массив сумм префиксов p[n] не является убывающим), вы можете найти элемент по сумме префиксов как запрос суммы префиксов по индексу из BIT, что занимает O(logn) времени. Единственное отличие состоит в том, что вам нужно сравнить сумму префикса, которую вы получаете на каждом уровне, с вашим вводом, чтобы решить, в каком поддереве вам нужно искать впоследствии - если сумма префикса меньше, чем ваш ввод, продолжайте поиск в левом поддереве; в противном случае ищите правое поддерево; повторяйте этот процесс, пока не достигнете узла, который суммирует желаемую сумму префикса, и в этом случае верните индекс узла. Идея аналогична бинарному поиску, потому что суммы префиксов естественным образом сортируются в BIT. Если в a[n] есть отрицательные значения, этот метод не будет работать, так как в этом случае суммы префиксов в BIT не будут сортироваться.
