离线树状数组的操作

## 一.单点修改 矩形询问 把矩形询问拆成4个前缀矩形的形式 这样可以保证每个修改对后面所有询问都有贡献 不用删除 然后把所有询问离线 按照$x$递增顺序排序 然后用类似于扫描线的方法 每次遇到修改在树状数组中修改 遇到矩形查询时查询一个前缀和 再加加减减就行了 ## 二.矩形修改 单点询问 把矩形转成差分的形式 在左下角加上 左上角+1处减去 右下角$x+1$处减去 右上角$x+1$处加上这样就可以保证$x$在此范围内的询问都有贡献 然后也是询问排序 直接查询前缀和就行了 ## 三.矩形修改 矩形询问 有点复杂 把修改矩形拆成4个后缀矩形 把询问矩形拆成4个前缀矩形 每次查询一个前缀矩形和一个后缀矩形的交中的值之和 这需要开4个树状数组 每次加入一个后缀矩形时 ```cpp bit1[i]=bit1[i]+z; bit2[i]=bit2[i]+z*(x-1); bit3[i]=bit3[i]+z*(y-1); bit4[i]=bit4[i]+z*(x-1)*(y-1); ``` 四个树状数组中分别加入 值 值$\times x-1$ 值$\times y-1$ 值$\times (x-1)\times (y-1)$ 查询时 ```cpp ret=ret+bit1[i]*x*y; ret=ret-bit2[i]*y; ret=ret-bit3[i]*x; ret=ret+bit4[i]; ``` 还是通过4个前缀矩形容斥的方法 $$ ans=z\times (x_q\times y_q-x_q(y_a-1)-y_q(x_a-1)+(x_a-1)(y_a-1)) $$ 到图上就是这样  红色是修改 蓝色是一个查询 查询时加上蓝色和紫色 减去两个绿色就行了 查询后四个矩形加加减减就可以了