Getting same issue with JAVA. Getting TLE after 15-16 cases

I think your code counts no. of elements smaller than **or equal to** k. To find no. of elements smaller than k, `lower_bound`

must be used instead of `upper_bound`

in the code for query function.

Can u please share the implementation of segment tree with pbds ?

@arunnsit Can you please tell me the memory complexity of this algorithm? Is it O(NlogN) or could be more?

It will be nlogn. Because every element will be present in logn parent vectors.

“A range L to R can divided into at most Log(N) parts” - can anyone please give any proof or clue about it…?

Check out my post about point updates in merge sort tree.

@arunnsit sir, Just a stupid doubt, the 0(LogN * LogN) for query is because of the binary search being used only on those segments which satisfy the [L,R] segment and the order of such [L,R] segment is 0(LogN). Right?

yes

Hii @arunnsit sir !!

I understood the starting part till query and build function.

And I am trying very hard to get my head around the point updates and policy based data structures part but I just can’t.

So can you please elaborate how we can do that with a sample code and policy based data structures ?

If we use store a set at each node of our segment tree, then computing the set for the parent will be O(n\text{ log }n) right? (Merging two sets).

Is there a way to handle point updates in a merge sort tree in O(\text{log }n)?

How is the complexity to build a merge sort tree O(nlogn) . For a segment tree, the time complexity to build is O(n), how it is O(nlogn) in merge sort tree . Can someone please help me understand.

same here bro