Intuition for O(log 𝑛) time complexity of the update and query operations in a Segment tree

I had posted an answer to similar question 5 years ago on quora. Reposting the same here.

Time complexity for query operations in a segment tree is O(log n) because there are O (log n) levels in a segment tree and at max we will have to process 4 nodes in a level. Let’s go through some pictures depicting a few arrangements which should give an idea why at max only 4 nodes are processed in a level.

We should keep in mind that the query is always for a continuous range.

First let us see some arrangements when we will have to process (or not process) 4 nodes in a level through some pictures.

Black nodes are totally overlapped nodes, half black nodes are partially overlapped nodes and white nodes of last level are the ones which are not at all in the query interval.

Case 1:

The above arrangement is not possible to have. Why ? As the query is for continuous range, we can not have a ‘not included’ node in between.

Case 2:

Even this arrangement is not possible because for this arrangement the parent of nodes A and B itself has been totally overlapped and the control will return from parent of A and B.

Case 3:

This is the one of the types of arrangement where 4 nodes will be processed. In this picture, the leftmost and rightmost nodes of interest are partially overlapped while other two nodes are totally overlapped w.r.t query interval.

We can extend based on the same idea for the next levels too and we will find that at no level more than 4 nodes are processed. For example:

Here also 4 nodes are processed but we can see these will either converge or at the max remain 4.

Now after we are done with analyzing the case where 4 nodes will be processed, is it possible to have a case where more than 4 nodes will be processed ? Only arrangements where more than 4 nodes can be processed should be an extension of case 3 ( as other arrangements are not valid ). Lets just check for 5 nodes by extending case 3.

Now it’s clearly visible that this arrangement is not possible. Why ? Because we can see the previous to ‘rightmost totally overlapped node’ is partially overlapped but (remember) our query is for continuous range.


Comments

New comments are not allowed.

Popular posts from this blog

END-TO-END ARGUMENTS IN SYSTEM DESIGN

END-TO-END ARGUMENTS IN SYSTEM DESIGN paper is one of the classic papers written by J.H. Saltzer, D.P. Reed and D.D. Clark. This paper discusses one of the design principles, called end-to-end argument , which provides guidance about where to place a function in layered systems. The paper argues that function implementation should be moved upward in layered systems - closer to the application that uses the function. Paper examines the end-to-end argument in detail using reliable data transmission in a communication system. "The function in question can completely and correctly be implemented only with the knowledge and help of the application standing at the end points of the communication system. Therefore, providing that questioned function as a feature of the communication system itself is not possible. (Sometimes an incomplete version of the function provided by the communication system may be useful as a performance enhancement.)." This paper examines the end-to-end ar
Read more