I recently came across an awesome tutorial on segment treee on codeforces. I understood the key concept of segment tree from this tutorial however I fail to understand below described section in the blog, which is about segment tree for array of length other then power of 2. Anyone please explain me how does this work with an example of both query and update operation.
We merge the 2 required nodes.
Say, my interval is [1,12]. Then my tree should be having nodes with following intervals-
[1,12]
[1,6] [7,12]
[1,3] [4,6] [7,9] [10,12]
[1,2] [3,3] [4,5] [6,6] [7,8] [9,9] [10,11] [12,12]
Other leaf nodes
Say I need interval [3,9]. For this, we will merge nodes [3,3] [4,6] [7,9] and get the answer.
Now you may ask why is it O(LogN) per query? Try to find the worst interval, i.e. the interval which needs merging of maximum nodes.
(PS: Implementations of Seg tree vary from coder to coder, some may have more optimised/efficient ones. I tried to describe the one in the blog)