前缀和以及差分

# 前缀和 ## 前缀和容易比较理解 假设这里有两个数组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]; } } } ```