树状数组区间加区间求和 and 历史版本和

spider_oyster · 2023-11-01 10:36:08 · 个人记录

其实很简单。

考虑只有区间加，即树状数组维护一个差分数组。

设 c_i 为树状数组位置 i 的值。

假设现在询问 sum(1,k)，即：\sum\limits_{1\leq i \leq k}\sum\limits_{1\leq j\leq i} c_j

可以发现第 j 个 c_j 出现了 k-j+1 次。

转化为求：(k+1)\sum\limits_{1\leq i\leq k} c_i-\sum\limits_{1\leq i\leq k} i\times c_i

直接维护即可。

struct BIT{
    int c1[N],c2[N];
    void upd(int x,int v) {for(int V=x*v;x<=n;x+=x&-x) c1[x]+=v,c2[x]+=V;}
    int sum(int x) {int s1=0,s2=0;for(int y=x;y;y^=y&-y) s1+=c1[y],s2+=c2[y];return (x+1)*s1-s2;}
    int qsum(int l,int r) {return sum(r)-sum(l-1);}
}tr;

下面说历史版本和。

引入时间的概念，记当前时间为 i。

考虑一个位置 j，这个位置之前有一些修改，第 k 次修改时间为 t_k，加的权值为 v_k，那么位置 j 的贡献为：

分别维护 \sum v_k 和 \sum v_k\times t_k 即可。

struct BIT{
    int c1[N],c2[N];
    void upd(int x,int v) {for(int V=x*v;x<=n;x+=x&-x) c1[x]+=v,c2[x]+=V;}
    int sum(int x) {int s1=0,s2=0;for(int y=x;y;y^=y&-y) s1+=c1[y],s2+=c2[y];return (x+1)*s1-s2;}
    int qsum(int l,int r) {return sum(r)-sum(l-1);}
}tr1,tr2;

void upd(int l,int r,int v,int t) //区间 [l,r] + v，当前时间为 t
{
    tr1.upd(l,v),tr1.upd(r+1,-v);
    tr2.upd(l,v*t),tr2.upd(r+1,-v*t);
}

int qsum(int l,int r,int t) {return tr1.qsum(l,r)*(t+1)-tr2.qsum(l,r);}

一些邪道：

区间覆盖 + 历史版本和：用 ODT + 树状数组。

区间取 max/min + 历史版本和：吉司机线段树，当线段树结点 mn[k]=mx[k]（区间值相同）的时候再用树状数组维护。复杂度显然是错的，但是没有人会想到这种做法 -> 没有人卡 -> 正确的。模拟赛用了好几次了，亲测有效。