Merge Sort Tree - Tutorial

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 ?

1 Like

@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.

2 Likes

“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.

2 Likes

@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?

@arunnsit sir, Sorry, but I didn’t get the complexity in the Bonus part. Can you explain that?

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 ?

1 Like

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