patternMinor
Finding the number of $L\leq j\leq R$ such that $a[j] \leq a[i]$
Viewed 0 times
suchnumberthethatfindingleq
Problem
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 :)
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 :)
Solution
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.
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.
Context
StackExchange Computer Science Q#45662, answer score: 2
Revisions (0)
No revisions yet.