sparshsinha123's blog

By sparshsinha123, history, 10 months 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.

Read more »

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

By sparshsinha123, history, 13 months ago, In English

Can anyone provide links to some codeforces problems on Tries?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By sparshsinha123, history, 14 months ago, In English

Given an array and two types of queries : set a[i] = a[i] xor K, for l <= i <= r for some K and give min over range [l,r]. Can it be done with lazy prop??

Read more »

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