树状数组学习笔记

树状数组有两个低级模式&＃xff0c;一个高级模式&＃xff08;万能&＃xff09;。
详细模板

低级模式一&＃xff1a;区间查询&＃43;单点修改&＃xff08;相当于有了单点查询&＃xff09;
初始化&＃xff1a;add(i,x)
单点修改&＃xff1a;cin x,y add(x,y) 把编号为x的修改为y值。
万能查询&＃xff1a;cin x,y cout qu(y)-qu(x-1) 单点查询时x,y相等。

低级模式二&＃xff1a;单点查询&＃43;区间修改&＃xff08;相当于有了单点修改&＃xff09;
初始化&＃xff1a;y&＃61;0–> i 1-n add(i,x-y) y&＃61;x
万能修改&＃xff1a;cin x,y,z add(x,z) add(y&＃43;1,-z) 把编号为x到y的修改为z值。
单点查询&＃xff1a;cin x cout qu(x)

高级模式&＃xff08;万能&＃xff09;:区间查询&＃43;区间修改&＃xff08;相当于啥都有&＃xff0c;不过复杂一点&＃xff09;
初始化&＃xff1a;y&＃61;0–> i 1-n add(i,x-y,0)&＃43;add(i,(x-y)i,1) y&＃61;x
万能修改&＃xff1a;cin x,y,z add(x,z,0) add(y&＃43;1,-z,0) add(x,zx,1) add(y&＃43;1,-z*(y&＃43;1),1)
万能查询&＃xff1a;cin x,y cout ask(y)-ask(x-1)

ask函数&＃xff1a;

int ask(int x)
{return ((x&＃43;1)*qu(x,0)-qu(x,1));
}