### sparshsinha123's blog

By sparshsinha123, history, 10 months ago,

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.

• +23

By sparshsinha123, history, 13 months ago,

Can anyone provide links to some codeforces problems on Tries?

• 0

By sparshsinha123, history, 14 months ago,

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??