Problem:↵
------------------↵
Given an array of n integers and q queries of the form: Q(L, R, x). ↵
For each query Q(L, R, x), you have to say "How many integers in the range L to R(inclusive) which are less than x".↵
↵
**There is no update operation.**↵
↵
### Constraints:↵
↵
- $1\leq n \leq 1900000$ ↵
- $1\leq q \leq 10^5$ ↵
↵
If I use Square Root Decomposition, complexity will be $O(q * sqrt(n) * log n )$, which is not so good for this constraints, I think### I know two ways:↵
↵
1. **Using SQRT decompostion:**↵
Partition the array in SQRT(n) blocks and Sort each block. Then for each query binary search(lower bound or upper bound) x in each block.↵
If I use Square Root Decomposition, complexity will be $O(q * sqrt(n) * log n )$, which is not so good for this constraints, I think.↵
↵
2. **Using segment tree:**↵
Store the sorted list of numbers in each node in the segment tree. Then for each query, binary search x at each required node.↵
↵
Can you please suggest any better solution for this problem ?↵
↵
Thanks in advance.
------------------↵
Given an array of n integers and q queries of the form: Q(L, R, x). ↵
For each query Q(L, R, x), you have to say "How many integers in the range L to R(inclusive) which are less than x".↵
↵
**There is no update operation.**↵
↵
### Constraints:↵
↵
- $1\leq n \leq 1900000$ ↵
- $1\leq q \leq 10^5$ ↵
↵
↵
1. **Using SQRT decompostion:**↵
Partition the array in SQRT(n) blocks and Sort each block. Then for each query binary search(lower bound or upper bound) x in each block.↵
If I use Square Root Decomposition, complexity will be $O(q * sqrt(n) * log n )$, which is not so good for this constraints, I think.↵
↵
2. **Using segment tree:**↵
Store the sorted list of numbers in each node in the segment tree. Then for each query, binary search x at each required node.↵
↵
Can you please suggest any better solution for this problem ?↵
↵
Thanks in advance.
