Диапазон запросов количество инверсии в O (LG N)

Question

Учитывая несортированный массив из п целых чисел, я знаю, что можно найти общее число инверсий, используя бит в O (N LG N) в соответствии с этим способом: Count Inversion by BIT

Однако возможно ли, что я должен запросить произвольный диапазон для общего числа инверсий в O (lg N)?

A O (N lg N) предварительное вычисление приемлемо.

Я провел некоторое исследование и, кажется, фактор N не может быть предотвращен ... Любые предложения будут оценены!

Answer 1

Это не тот ответ, за который вы смотрите, но у меня есть два предложения.

Во-первых, я не думаю, что BIT - это правильная структура данных, используемая для проблемы, которую вы пытаетесь решить. Преимуществом BIT является то, что он поддерживает O (lg n) запрашиваемую префиксную сумму, используя только O (lg n) для каждой вставки. Поскольку вы не вставляете, как только ваша структура данных будет завершена, BIT не будет выгодным (потому что вы можете использовать простой массив префиксных сумм, который можно запросить в O (1)).

Во-вторых, у меня есть наивные алгоритм, который использует O (N) во времени и пространстве, чтобы построить структуру данных, которая может найти инверсий дальности в O (1) Время:

Во-первых, построить (п X n) матрица, отображающая инверсии, так что mat[i][j]=1 только если i<j и arr[i] и arr[j] инвертированы. Затем вычислите префиксную сумму по каждой строке этой матрицы, так что mat[i][j] - это число инверсий с участием arr[i] в диапазоне [i,j]. Наконец, вычислите суффиксную сумму по каждому столбцу, так что mat[i][j] - это общее количество инверсий в диапазоне [i,j].

for i from 0 to n-2 
    for j from i+1 to n-1 
    if(arr[j] > arr[i]) 
     mat[i][j] = 1; 
for i from 0 to n-2 
    for j from i+1 to n-1 
    mat[i][j] += mat[i][j-1]; 
for j from n-1 to 1 
    for i from j-1 to 0 
    mat[i][j] += mat[i+1][j]; 

Это явно занимает O (N 2 ) время и пространство, но число инверсий в любом диапазоне может быть запрошен в постоянное время.