Is it possible to perform such operations with array in quasilinear total time (precalculations and queries)? 1. add a number x on a segment [l;r] 2. count the number of all elements in [l;r] which are <x If it is possible to solve this problem offline, then a new question arises: is it possible to solve it online with amortized O(log(n)^k) time per query (where k is a constant)?

I know that if a number is added to only one element (pos), then the problem can be solved in O(log(n)^2) time per query online using a segment tree with a treap in each node which consists of the elements of the segment which corresponds to the node. I also know that the given problem can be solved in O(sqrt(n)*log(n)) time per query (again, this works online) using sqrt-decomposition (we divide our array into sqrt(n) blocks of the size of sqrt(n), and then we maintain for each block it sorted and a modifier which is added to all the block's elements). But here the query time is too long.