前缀和以及差分

2018-02-01 15:33:58


前缀和

前缀和容易比较理解 假设这里有两个数组a[滑稽],b[滑稽]

下标 1 2 3 4 5

A组 1 3 5 7 9

S组 1 4 9 16 25

如果要求区间和,小一点还要算,但是值多了就会TLE【超过时间】于是就想到用一个S数组来存下标N到下标1的和,要算N到N+10的和就可以用S[N+10]的值减去S[N-1]的值 【一定是N-1!!不是N!!】

例如在上面,如要算下标为3到下标为5的和,只用S[5]=25,S[2]=4,和就等于S[5]-S[2]=21

公式1:S[i]=S[i-1]+A[i].算前缀和数组

公式2: 区间和=S[i]-S[n-1] n表示起始位置,i表示末位置

差分

1.一维差分

我们对[L,R]区间进行加num操作,在C[L]处加上num,在C[R+1]处减去num差分可以 O(1)处理 O(n)求和

void init(int l,int r,int num) {
    dis[l] += num, dis[r + 1] -= num;
}

int get() {
    for(int i = 1; i <= n; i++) {
        val[i] = val[i-1] + dis[i];
    }
}

2.二维差分

void init(int x1, int y1, int x2, int y2, int num) {
    sum[x1][y1] += num;
    sum[x1][y2 + 1] -= num;
    sum[x2 + 1][y1] -= num;
    sum[x2 + 1][y2 + 1] += num;
}

void get() {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            sum[i][j] += sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
        }
    }
}

3.树上差分

(1)点差分

对u 到v的路径上的点+num

用来求 - 已知路径求树上所有节点被路径覆盖次数

int init(int u, int v, int num) {
    dis[u] += num;
    dis[v] += num;
    dis[lca(u,v)] -= num;
    dis[f[lca(u,v)]] -= num;
}

(2)边差分

对 u 到 v 的路径上的边 +num

用来求 - 已知路径求被所有路径覆盖的边

dis[i] 表示以i节点为儿子的边

int init(int u, int v, int num) {
    dis[u] += num;
    dis[v] += num;
    dis[lca(u,v)] -= 2 *num;
}

最后dfs遍历一遍

void dfs(int x) {
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v != f[x][0]) {    //f[x][0] 为倍增数组 
            dfs(v);
            dis[x] += dis[v];
        }
    }
}