3
$\begingroup$

I have recently encountered the following problem which I heard can be solved by using BIT (binary indexed trees) but I am not sure how:

Given an array $a[1, 2, \ldots, n]$ and $Q$ queries of the form $(L, R, i)$ $(L\leq i\leq R)$. For each query, you have to print the number of $j$ such that $L\leq j\leq R$ and $a[j] \leq a[i]$.

I tried coordinate compression and then sorting the queries by increasing order of $i$ (answering the queries offline), but the L, R part make things hard. I think we can convert the query $(L, R, i)$ into two parts $(1, R, i)$ and $(1, L-1, i)$ (and subtract them), but how to find the answer for that either?

Also note that this problem can be solved by Mo's algorithm, but I am looking for something like $O(q \log n)$ or $O (q \log^2 n)$ (maybe binary search on the answer and do some magic with bits?).

Thanks :)

$\endgroup$
2
$\begingroup$

Here is a solution in time $O((Q+n)\log^2 n)$ and space $O(n\log n)$. For simplicity, assume that $n$ is a power of $2$, and that the array is zero-based.

A dyadic interval is an interval of the form $[c \cdot 2^k,(c+1) \cdot 2^k)$ (that is, $c\cdot 2^k,\ldots,(c+1)\cdot 2^k-1$). For example, when $n = 8$ we have the following dyadic intervals: $$ [0,8),[0,4),[4,8),[0,2),[2,4),[4,6),[6,8), \\ [0,1),[1,2),[2,3),[3,4),[4,5),[5,6),[6,7),[7,8). $$ Each interval of the form $[0,x)$ is the disjoint union of at most $\log_2 n$ slices. For example, for $n = 8$ we have (for $x \neq 1,2,4,8$): $$ [0,3) = [0,2) \cup [2,3), \\ [0,5) = [0,4) \cup [4,5), \\ [0,6) = [0,4) \cup [4,6), \\ [0,7) = [0,4) \cup [4,6) \cup [6,7). $$

A dyadic slice of the array $a$ consists of the elements $a[s],\ldots,a[t]$ for some dyadic interval $s,\ldots,t$.

As preprocessing, we sort (separately) each dyadic slice of $a$. This takes time $O(n\log^2 n)$ and consumes space $O(n\log n)$ (since each index participates in $\log_2 n$ slices).

As mentioned in the question, it is enough to handle the following type of query:

Given $i,R$, count the number of indices $j <R$ such that $a[j] \leq a[i]$.

Given $i,R$, we retrieve $a[i]$, and present $[0,R)$ as a union of $O(\log n)$ dyadic intervals $I_1,\ldots,I_m$. Using binary search, for each $k$ we determine the number of indices $j \in I_k$ such that $a[j] \leq a[i]$. This takes time $O(\log^2 n)$ (altogether). Summing these numbers, we arrive at the answer to the query.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.