Alioth_ 的博客

Alioth_ 的博客

离线树状数组的操作

posted on 2020-02-13 09:14:40 | under 知识点 |

一.单点修改 矩形询问

把矩形询问拆成4个前缀矩形的形式 这样可以保证每个修改对后面所有询问都有贡献 不用删除 然后把所有询问离线 按照$x$递增顺序排序 然后用类似于扫描线的方法 每次遇到修改在树状数组中修改 遇到矩形查询时查询一个前缀和 再加加减减就行了

二.矩形修改 单点询问

把矩形转成差分的形式 在左下角加上 左上角+1处减去 右下角$x+1$处减去 右上角$x+1$处加上这样就可以保证$x$在此范围内的询问都有贡献 然后也是询问排序 直接查询前缀和就行了

三.矩形修改 矩形询问

有点复杂

把修改矩形拆成4个后缀矩形 把询问矩形拆成4个前缀矩形 每次查询一个前缀矩形和一个后缀矩形的交中的值之和 这需要开4个树状数组 每次加入一个后缀矩形时

        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)$

查询时

        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)) $$ 到图上就是这样

红色是修改 蓝色是一个查询 查询时加上蓝色和紫色 减去两个绿色就行了

查询后四个矩形加加减减就可以了