Merge Sort Tree - Tutorial

tutorial
, ,
17

Why do you think log2(10^5) * 10^5 vectors are required? vectors should be equal to number N+N/2+N/4+N/8…(i.e number of nodes in segtree) Which is 2N but we require a number which is multiple of 2 and greater than 2N. So to be on safe side we usually take 4*N nodes in segtree.

1 Like
18

Oh yes! I got confused. Thanks

19

yeah, Persistent Segment Tree can solve such problems but do you think its as easy to explain and understand as this?

1 Like
20

maybe. After all, the only important things -after understand segment tree in its pointer implementation- are:
-In each update, at most logN node change
-In each update, create a new version of all nodes changed

21

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

22

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.

1 Like
23

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

1 Like
24

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

25

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

2 Likes
26

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

27

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

2 Likes
28

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

35

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

36

yes

37

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
38

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

39

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.

41

same here bro

43

DSU on the tree has a similar idea.

44

This code is easy to understanf:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2 # Find the middle of the list
left_half = arr[:mid] # Divide the list into two halves
right_half = arr[mid:]

    merge_sort(left_half)  # Recursive call to sort the left half
    merge_sort(right_half)  # Recursive call to sort the right half

    i = j = k = 0  # Initialize iterators for the left, right, and merged lists

    # Merge the two halves back together
    while i < len(left_half) and j < len(right_half):
        if left_half[i] < right_half[j]:
            arr[k] = left_half[i]
            i += 1
        else:
            arr[k] = right_half[j]
            j += 1
        k += 1

    # Check if any elements were left
    while i < len(left_half):
        arr[k] = left_half[i]
        i += 1
        k += 1

    while j < len(right_half):
        arr[k] = right_half[j]
        j += 1
        k += 1

Example usage:

arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print(“Sorted array:”, arr)