segment-tree2

Posted on | In ,

segment-tree2: how to deal with both plus and muiltiply operate of segments?

2018/10/31 10:03 (UTC+8) China

when you need to search down a node,you should erase the “lazy” tag and update the subnodes(pushdown).in the past,the operate is only plus. it may be like this:

[x+a+b+c+d]=[x]+(a+b+c+d)

so if you don’t want to search down,you can remenber “a+b+c+d” as an “lazy” tag.

but now,muiltiply operate has added.so,it may be like this:

[(((x+a)*b)+c)*d)]=(a*d)*[x]+(a*b*d+c*d)

so,it’s time to expand the “lazy” tag.

define

1
2
3
4
struct tag
{
    int k,b;                    //k*[x]+b
}

operate

so,how to update the tag? it’s esay when k or b is 0. in other cases,we should use some math formulas.

  • plus

k*[x]+b+(pa)=k*[x]+(b+pa)

just simply merge “b”.

  • muiltiply

(k*[x]+b)(pa)=(k\pa)[x]+(bpa)

  • combine

(((k*[x]+b)*(pa))*pa1)+(pa2)=(k*pa1)*[x]+(b*pa1+pa2)

of course,using “distributibe law of muiltiply”,we should muiltiply both “k” and “b”.

here are the code:

1
锟斤拷 !@#$qwer 烫烫烫