Segment trees

Правка en1, от _Bishop_, 2020-07-01 14:26:08

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский _Bishop_ 2020-07-01 14:26:08 1069 Initial revision (published)