poj 3109
注意線段樹插入時是整個路徑都要tot+x,而find時,如果 if(l<=left&&right<=r)return tot
lazy定理,雖然說要對整個線段都更新,
用在整段更新的 到l<=left&&right<=r即可,也即上面的都更新,但是后面的等到要查詢時再更新,即
if(inc[p]){
inc[2*p]+=inc[p];
inc[2*p+1]+=inc[p];
}
inc[p]=0;
poj 3468
開這樣吧, MAXN*4,3倍會RE?
if(l<=left&&right<=r)就return 否則遞歸到底層,線段樹不起作用了
3667 左連續的最大值,最大值,右連續的最大值
poj 3368 三個數據的應用很廣泛。。lmax,rmax,max
線段樹的最重要特點就是把有共同點的零散信息整合到一起 。就是說,線段數是把各個節點共同所需記錄的信息,記錄在它們的父親節點上。這樣,它就省去不斷重復操作而造成的冗雜。從而,大大優于普通數組操作。