_Bishop_'s blog

Segment trees
By _Bishop_, history, 4 years ago, In English

Consider a segment tree with lazy propagation built on an array. Let it support the following operations $$$f_{update}(l , r)$$$ and $$$f_{query}(l,r)$$$. Here , $$$f_{update}(l , r)$$$ is the range update operation from index $$$l$$$ to $$$r$$$ on the array and $$$f_{query}(l,r)$$$ is the query operation on range $$$l$$$ to $$$r$$$. How to decide mathematically(or intuitively) whether a particular combination of $$$f_{update}$$$ and $$$f_{query}$$$ will work efficiently or not? For instance the following combinations : $$$f_{update}$$$ = $$$increment$$$ $$$each$$$ $$$value$$$ $$$in$$$ $$$interval$$$ $$$by$$$ $$$some$$$ $$$fixed$$$ $$$value$$$ $$$v$$$ and $$$f_{query}$$$ = $$$get$$$ $$$maximum$$$ $$$of$$$ $$$range$$$ works good. However, $$$f_{update}$$$ = $$$take$$$ $$$max$$$ $$$of$$$ $$$each$$$ $$$element$$$ $$$in$$$ $$$l$$$ $$$to$$$ $$$r$$$ $$$with$$$ $$$v$$$ and $$$f_{query}$$$ = $$$get$$$ $$$maximum$$$ $$$of$$$ $$$range$$$ is not that obvious . More formally, what are the conditions that we must check on $$$f_{update}$$$ and $$$f_{query}$$$ to quickly decide whether the combination can be used efficiently or not? Also, if possible please provide some standard combinations that can be done and those that can't.

  • Vote: I like it
  • +23
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

To answer the question, first of all let's define three auxiliary functions: $$$merge()$$$, $$$combine()$$$ and $$$apply()$$$

Let me first explain what these functions do:-

$$$merge(nodeLeft,nodeRight)$$$ — This is the main operation of the segment tree, for example, if you want range sum queries, this returns the sum of left and right, if you want $$$min$$$, $$$max$$$ or $$$gcd$$$, it returns that.

$$$combine(update1,update2)$$$ — This function is responsible for lazy propagation. Basically what it does is, it combines two different updates into a single update, for example, if one of your update is $$$\text{add 17}$$$ and the other update is $$$\text{add 9}$$$, then on combining these two updates you should get $$$\text{add 26}$$$. For more complex type of updates (like addition of fibonacci on a range) this function can be very complicated.

$$$apply(node,update)$$$ — This is the answer to your question. In this function, you're actually applying the update to a node. As an example, let's consider the update "$$$\text{add 5 to all the elements in the range[L,R]}$$$", suppose the current node lies fully within that interval, then in the $$$apply()$$$ function you have to add $$$(widthOfNode)*5$$$ to this node. For addition updates, this function is pretty easy. But if the update is more complicated then it's not easy to store the correct new information efficiently.

It is not possible to make a lazy propagation segtree without implementing the above three operations.

Here is my implementation of a generic segment tree. I have created two structs for node and update which have the above 3 functions implemented. This segment tree supports range addition updates and range maximum queries, however the functioning can be changed by changing just the above 3 functions. (There is an extra function $$$check()$$$ which is irrelevant to the current question and is used for generic segment tree descent, I might describe it later in a separate blog)

So the answer to your question is — If you can think of a way to implement these 3 functions, then you can make a segment tree using these. As far as, "replace with max on range update" and "sum query" is concerned, it is easy to make the $$$merge$$$ and $$$combine$$$ functions but the $$$apply$$$ function is hard, because you need to know the new sum of the elements in the range after the update is applied. However, jiry_2 has explained Segment Tree Beats in his blog which does the exact same thing.

→ Reply
»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

your name is fenwick and u are asking doubt related to segment tree. i found it funny :) hhahahaha

→ Reply