How to find the count of elements in a given range ( l, r ) in an array whose value is <= k where k is a given value? I have found the solutions using BIT and square root decomposition. Can anyone provide a code using segment trees? There are number of queries and in each query the value of k changes.
This question is from Numbers less than X of a range in an array - Codeforces
I was unable to understand. Can anyone help me?
Assume that there are no updates.
Please post the question link, so I know that you aren’t asking a question from an ongoing contest.
I have modified this question.
k is not constant for all queries
Oh, then it should be Segment Tree + Mo’s algorithm(which is sadly square root decomposition + offline queries)
The online and offline versions of this problem are very different. I think there are O(\log{n}) per query solutions for both, but offline is much simpler. Which do you want?
Isn’t offline Mo’s algorithm? And how will you do online? Please enlighten me
Offline: sort queries by k, and initialize a fenwick tree with an array of length n initially filled with zeros. Then, keep a pointer to a sorted version of the original array, and as elements become \leq k for the k of the current query, set the value at the element’s index in the fenwick tree to 1. Then just do a sum query on the query’s range.
Online: do the same thing, but with a persistent segment tree. Or use a wavelet tree (the link in the blog doesn’t work, but read the comments or look stuff up further). For updates, a mergesort tree will work (note that you’ll need a PBDS set in each node instead of a vector).
For more Detail you can Read this comment
Link for Wavelet Tree