• `算法竞赛知识` 前缀和与差分

    catalog

    前缀和与差分

    前缀和 与 差分, 两者其实是互逆的.
    比如一个数组A的 前缀和数组为: 数组B
    则, 数组B的 差分数组 为 数组A

    这一点是非常重要的! 两者是同时存在的!

    应用

    定义范围为: (一维的区间) (二维的矩形) (三维的矩阵) 且所有边均与坐标轴平行

    前缀和: 只支持 查询 (范围里 所有A[]元素) 之和
    差分: 只支持 对(范围里 所有A[]元素) 进行**+= K操作**

    空间前缀和

    根据数组A[] (其代表一个n维空间, 一维区间/二维矩形/三维矩阵), 求其前缀和数组

    比如一维A[N], 二维A[N][M], 三维A[N][M][Z],
    我们称: (0) (0,0) (0,0,0)点为 空间原点,
    (N-1) (N-1,M-1) (N-1,M-1,Z-1)点为 空间临界点

    空间前缀和数组Sum, 有起点和终点的概念.
    因为Sum[ x]的定义是: 从 ∑ i = 起点 x A [ i ] \sum_{i = 起点}^{x}{A[ i]} ∑i=起点x​A[i]
    因此, 必须要规定哪里为起点.
    一般, 我们选取: 原点 作为 起点, 临界点作为 终点

    这样, 前缀和的定义为:
    { 一维空间 : S u m [ x ] = ∑ i = 0 x A [ i ] 二维空间 : S u m [ x ] [ y ] = ∑ i = 0 x ∑ j = 0 y A [ i ] [ j ] 三维空间 : S u m [ x ] [ y ] [ z ] = ∑ i = 0 x ∑ j = 0 y ∑ k = 0 z A [ i ] [ j ] [ k ]

    {一维空间:Sum[x]=∑i=0xA[i]二维空间:Sum[x][y]=∑i=0x∑j=0yA[i][j]三维空间:Sum[x][y][z]=∑i=0x∑j=0y∑k=0zA[i][j][k]" role="presentation" style="position: relative;">{一维空间:Sum[x]=∑i=0xA[i]二维空间:Sum[x][y]=∑i=0x∑j=0yA[i][j]三维空间:Sum[x][y][z]=∑i=0x∑j=0y∑k=0zA[i][j][k]
    ⎩ ⎨ ⎧​一维空间:Sum[x]=∑i=0x​A[i]二维空间:Sum[x][y]=∑i=0x​∑j=0y​A[i][j]三维空间:Sum[x][y][z]=∑i=0x​∑j=0y​∑k=0z​A[i][j][k]​

    这个定义, 确实直观, 也很简单.

    查询

    由于范围的定义, 其所有边均与坐标轴平行, 因此对于任意一个范围, 不管是几维度的, 其均可以用两个点来表示
    … 比如N维空间, 其范围有2^N个端点.
    定义为l和r这两个点. l为该范围内 离原点最近的 端点, r为该范围内离原点最远的端点
    … 比如l = (a, b, c) r = (d, e, f); 则该范围的所有端点为: (a/d, b/e, c/f) (共2^N个)

    令l的坐标为: xl, yl, zl, .., r的坐标为: xr, yr, zr, ..., 以适应不同维度空间

    { 一维空间 : ∑ i ∈ 范围 [ l , r ] A [ i ] = ( S u m [ x r ] − S u m [ x l − 1 ] ) 二维空间 : ∑ i ∈ 范围 [ l , r ] A [ i ] = ( S u m [ x r , y r ] − S u m [ x l − 1 , y r ] − S u m [ x r , y l − 1 ] + S u m [ x l − 1 , y l − 1 ] ) 三维空间 : ∑ i ∈ 范围 [ l , r ] A [ i ] = ( S u m [ x r , y r , z r ] − S u m [ x l − 1 , y r , z r ] − S u m [ x r , y l − 1 , z r ] − S u m [ x r , y r , z l − 1 ] + S u m [ x l − 1 , y l − 1 , z r ] + S u m [ x l − 1 , y r , z l − 1 ] + S u m [ x r , y l − 1 , z l − 1 ] − S u m [ x l − 1 , y l − 1 , z l − 1 ]

    {一维空间:∑i∈范围[l,r]A[i]=(Sum[xr]−Sum[xl−1])二维空间:∑i∈范围[l,r]A[i]=(Sum[xr,yr]−Sum[xl−1,yr]−Sum[xr,yl−1]+Sum[xl−1,yl−1])三维空间:∑i∈范围[l,r]A[i]=(Sum[xr,yr,zr]−Sum[xl−1,yr,zr]−Sum[xr,yl−1,zr]−Sum[xr,yr,zl−1]+Sum[xl−1,yl−1,zr]+Sum[xl−1,yr,zl−1]+Sum[xr,yl−1,zl−1]−Sum[xl−1,yl−1,zl−1]" role="presentation" style="position: relative;">{一维空间:∑i∈范围[l,r]A[i]=(Sum[xr]−Sum[xl−1])二维空间:∑i∈范围[l,r]A[i]=(Sum[xr,yr]−Sum[xl−1,yr]−Sum[xr,yl−1]+Sum[xl−1,yl−1])三维空间:∑i∈范围[l,r]A[i]=(Sum[xr,yr,zr]−Sum[xl−1,yr,zr]−Sum[xr,yl−1,zr]−Sum[xr,yr,zl−1]+Sum[xl−1,yl−1,zr]+Sum[xl−1,yr,zl−1]+Sum[xr,yl−1,zl−1]−Sum[xl−1,yl−1,zl−1]
    ⎩ ⎨ ⎧​一维空间:∑i∈范围[l,r]​A[i]=(Sum[xr]−Sum[xl−1])二维空间:∑i∈范围[l,r]​A[i]=(Sum[xr,yr]−Sum[xl−1,yr]−Sum[xr,yl−1]+Sum[xl−1,yl−1])三维空间:∑i∈范围[l,r]​A[i]=(Sum[xr,yr,zr]−Sum[xl−1,yr,zr]−Sum[xr,yl−1,zr]−Sum[xr,yr,zl−1]+Sum[xl−1,yl−1,zr]+Sum[xl−1,yr,zl−1]+Sum[xr,yl−1,zl−1]−Sum[xl−1,yl−1,zl−1]​
    公式中涉及到(下标越界)的地方, 需以0来替代

    公式看着很复杂, 其实涉及到 容斥原理, 有几点可以帮助理解:

    • Sum的项数, 等于 2^N. 其实每一项, 代表范围的各个端点.
    • 先抛开x y等不谈, 单看-1操作, 每个维度都有0 和 -1两种选择.
      比如, 二维空间, 其为: (0, 0) (-1, 0) (0, -1) (-1, -1)
    • 一个端点中-1个数为奇数, 则该项是负号; 否则为正号.
      比如, [0, -1, -1]为正号.
    • -1作用的对象 (即-1的前面), 一定是l端点的坐标!!
      即, 不会出现: xr - 1 yr - 1 zr - 1 ! 这一点很重要.

    构造

    从定义式看, Sum[]可以通过 N层for循环来求出.

    但Sum有递推式, 可以O(1)求出.
    假设当前要求Sum[ x][ y], 且对于所有Sum[ <=x][ <=y]均已求出.

    利用上面的查询公式, 当查询范围l == r == 当前(x, y)时,此时有:
    ∑ i ∈ 范围 [ l , r ] A [ i ] = A [ x ] [ y ] = S u m [ x ] [ y ] − S u m [ x − 1 ] [ y ] − S u m [ x ] [ y − 1 ] + S u m [ x − 1 ] [ y − 1 ] \sum_{i \in 范围[l, r]}{A[ i]} = A[x][y] = Sum[ x][ y] - Sum[ x - 1][ y] - Sum[ x][ y - 1] + Sum[ x - 1][ y - 1] ∑i∈范围[l,r]​A[i]=A[x][y]=Sum[x][y]−Sum[x−1][y]−Sum[x][y−1]+Sum[x−1][y−1]

    则有: Sum[ x][ y] = A[ x][ y] + Sum[ x - 1][ y] + Sum[ x][ y - 1] - Sum[ x - 1][ y - 1]

    看似与查询很相似, 都是2^N个项, 也都是-1 和 0选与不选的组合.
    但有一点, 与查询相反, - 1为奇数的项 是正号.

    for循环从起点开始遍历, 则可以O(L^N)的构造前缀和数组. L为矩阵长, N为空间维度

    空间差分

    差分的定义比较复杂, 不像前缀和那样明了, 因此在介绍差分定义前, 先了解下差分与前缀和的关系

    前面提过, 差分和前缀和是互逆的, 因此, 有了前缀和的定义, 来反推: 差分的定义.

    数组A的 差分数组为 数组B;
    则一定有: 数组B的 前缀和数组为 数组A;

    这样讲不是太严谨, 因为从前缀和知道, 他有一个起点/终点问题.
    而差分, 也是有起点和终点问题.

    所以严格讲, 上面命题成立的前提是: 两者的起点是相同的.
    比如, 前缀和的起点是原点, 则差分的起点也必须是原点
    比如, 差分的起点是临界点, 则前缀和的起点也必须是临界点

    规定起点为原点.
    数组Sum的 差分数组为 数组Diff;
    则一定有: 数组Diff的 前缀和数组为 数组Sum;

    由前缀和 的查询公式的定义有:
    查询范围为[l, r], 其中: l = (xl, yl, zl), r = (xr, yr, zr)
    { 一维空间 : ∑ i ∈ 范围 [ l , r ] A [ i ] = ( S u m [ x r ] − S u m [ x l − 1 ] ) 二维空间 : ∑ i ∈ 范围 [ l , r ] A [ i ] = ( S u m [ x r , y r ] − S u m [ x l − 1 , y r ] − S u m [ x r , y l − 1 ] + S u m [ x l − 1 , y l − 1 ] ) 三维空间 : ∑ i ∈ 范围 [ l , r ] A [ i ] = ( S u m [ x r , y r , z r ] − S u m [ x l − 1 , y r , z r ] − S u m [ x r , y l − 1 , z r ] − S u m [ x r , y r , z l − 1 ] + S u m [ x l − 1 , y l − 1 , z r ] + S u m [ x l − 1 , y r , z l − 1 ] + S u m [ x r , y l − 1 , z l − 1 ] − S u m [ x l − 1 , y l − 1 , z l − 1 ]

    {一维空间:∑i∈范围[l,r]A[i]=(Sum[xr]−Sum[xl−1])二维空间:∑i∈范围[l,r]A[i]=(Sum[xr,yr]−Sum[xl−1,yr]−Sum[xr,yl−1]+Sum[xl−1,yl−1])三维空间:∑i∈范围[l,r]A[i]=(Sum[xr,yr,zr]−Sum[xl−1,yr,zr]−Sum[xr,yl−1,zr]−Sum[xr,yr,zl−1]+Sum[xl−1,yl−1,zr]+Sum[xl−1,yr,zl−1]+Sum[xr,yl−1,zl−1]−Sum[xl−1,yl−1,zl−1]" role="presentation" style="position: relative;">{一维空间:∑i∈范围[l,r]A[i]=(Sum[xr]−Sum[xl−1])二维空间:∑i∈范围[l,r]A[i]=(Sum[xr,yr]−Sum[xl−1,yr]−Sum[xr,yl−1]+Sum[xl−1,yl−1])三维空间:∑i∈范围[l,r]A[i]=(Sum[xr,yr,zr]−Sum[xl−1,yr,zr]−Sum[xr,yl−1,zr]−Sum[xr,yr,zl−1]+Sum[xl−1,yl−1,zr]+Sum[xl−1,yr,zl−1]+Sum[xr,yl−1,zl−1]−Sum[xl−1,yl−1,zl−1]
    ⎩ ⎨ ⎧​一维空间:∑i∈范围[l,r]​A[i]=(Sum[xr]−Sum[xl−1])二维空间:∑i∈范围[l,r]​A[i]=(Sum[xr,yr]−Sum[xl−1,yr]−Sum[xr,yl−1]+Sum[xl−1,yl−1])三维空间:∑i∈范围[l,r]​A[i]=(Sum[xr,yr,zr]−Sum[xl−1,yr,zr]−Sum[xr,yl−1,zr]−Sum[xr,yr,zl−1]+Sum[xl−1,yl−1,zr]+Sum[xl−1,yr,zl−1]+Sum[xr,yl−1,zl−1]−Sum[xl−1,yl−1,zl−1]​

    当查询范围l == r == 当前(x, y)时, 利用上面的公式, 可以得到差分定义有:
    { 一维空间 : ∑ i ∈ 范围 [ l , r ] D i f f [ i ] = D i f f [ x ] = S u m [ x ] − S u m [ x − 1 ] 二维空间 : ∑ i ∈ 范围 [ l , r ] D i f f [ i ] = D i f f [ x ] [ y ] = S u m [ x ] [ y ] − S u m [ x − 1 ] [ y ] − S u m [ x ] [ y − 1 ] + S u m [ x − 1 ] [ y − 1 ] 三维空间 : ∑ i ∈ 范围 [ l , r ] D i f f [ i ] = D i f f [ x ] [ y ] [ z ] = S u m [ x ] [ y ] [ z ] − S u m [ x − 1 ] [ y ] [ z ] − S u m [ x ] [ y − 1 ] [ z ] − S u m [ x ] [ y ] [ z − 1 ] + S u m [ x − 1 ] [ y − 1 ] [ z ] + S u m [ x − 1 ] [ y ] [ z − 1 ] + S u m [ x ] [ y − 1 ] [ z − 1 ] − S u m [ x − 1 ] [ y − 1 ] [ z − 1 ] 下标越界处 , 视为 0

    {一维空间:∑i∈范围[l,r]Diff[i]=Diff[x]=Sum[x]−Sum[x−1]二维空间:∑i∈范围[l,r]Diff[i]=Diff[x][y]=Sum[x][y]−Sum[x−1][y]−Sum[x][y−1]+Sum[x−1][y−1]三维空间:∑i∈范围[l,r]Diff[i]=Diff[x][y][z]=Sum[x][y][z]−Sum[x−1][y][z]−Sum[x][y−1][z]−Sum[x][y][z−1]+Sum[x−1][y−1][z]+Sum[x−1][y][z−1]+Sum[x][y−1][z−1]−Sum[x−1][y−1][z−1]" role="presentation" style="position: relative;">{一维空间:∑i∈范围[l,r]Diff[i]=Diff[x]=Sum[x]−Sum[x−1]二维空间:∑i∈范围[l,r]Diff[i]=Diff[x][y]=Sum[x][y]−Sum[x−1][y]−Sum[x][y−1]+Sum[x−1][y−1]三维空间:∑i∈范围[l,r]Diff[i]=Diff[x][y][z]=Sum[x][y][z]−Sum[x−1][y][z]−Sum[x][y−1][z]−Sum[x][y][z−1]+Sum[x−1][y−1][z]+Sum[x−1][y][z−1]+Sum[x][y−1][z−1]−Sum[x−1][y−1][z−1]
    \\ \quad 下标越界处, 视为0 ⎩ ⎨ ⎧​一维空间:∑i∈范围[l,r]​Diff[i]=Diff[x]=Sum[x]−Sum[x−1]二维空间:∑i∈范围[l,r]​Diff[i]=Diff[x][y]=Sum[x][y]−Sum[x−1][y]−Sum[x][y−1]+Sum[x−1][y−1]三维空间:∑i∈范围[l,r]​Diff[i]=Diff[x][y][z]=Sum[x][y][z]−Sum[x−1][y][z]−Sum[x][y−1][z]−Sum[x][y][z−1]+Sum[x−1][y−1][z]+Sum[x−1][y][z−1]+Sum[x][y−1][z−1]−Sum[x−1][y−1][z−1]​下标越界处,视为0

    以上, 就是对于(起点为原点)的 差分定义.

    对于[ i]位置,
    前缀和Sum[ < i] = Diff[ 0] + Diff[ 1] + ... + Diff[ < i], 即Sum[ < i]里, 都没有Diff[ i]
    而前缀和Sum[ >= i] = Diff[ 0] + Diff[ 1] + ... + Diff[ >= i], 都有Diff[ i]
    即, 如果我们修改Diff[ i] (比如+= k, 对于Sum[ < i]是不会影响的, 而对于所有的Sum[ >= i] 均会使其+= k

    即如果我们想将Sum[ l, l+1, ...., r] += k, 如果单独执行Sum[ i] += k, 则时间是O(n)的.
    而对应到其差分为: Diff[ l] += k, Diff[ r + 1] -= k

    也就是, 如果要对范围[l, r]进行+= k操作, 其对应的差分为: [l]. [r + 1]
    这一点, 和前缀和恰好是相反的. 前缀和的区间[l, r]对应的是: [r], [l - 1]

    因为, 差分的Diff[ i]其代表的(影响的)是 Sum[ i, ..., 终点]这些元素
    而前缀和的Sum[ i]代表的是 Diff[ i, ..., 起点]这些元素. 一个是到终点, 一个是起点, 正好相反

    其实有办法将差分, 也变成 [r], [l - 1]; 这样, 前缀和与差分就统一了.

    规定 起点为临界点, 终点为原点.
    即, Diff[ i] = Sum[ i] - Sum[ i + 1]

    • 此时, 修改Sum[ l, ..., r] += k, 等价于: Diff[ r] += k Diff[ l - 1] -= k
    • 但要注意, 差分与前缀和是互逆的. 差分的起点为临界点, 则前缀和的起点也必须是临界点.
      即Sum[ i] = Diff[ i, ..., 起点] = Diff[ i, ..., 临界点] (即现在的Sum[i]其实是后缀和)

    修改

    将范围[l, r]的所有Sum[]均+= k, 则对应的差分操作为: (令l = (xl, yl, zl), r = (xr, yr, zr))
    其中的 ‘ + k ‘ 表示累加 k { 一维空间 : S u m [ i ∈ 范围[l, r] ] + k  ⇔ ( S u m [ x r ] + k ; S u m [ x l − 1 ] − k ; ) 二维空间 : S u m [ i ∈ 范围[l, r] ] + k  ⇔ ( S u m [ x r , y r ] + k ; S u m [ x l − 1 , y r ] − k ; S u m [ x r , y l − 1 ] − k ; S u m [ x l − 1 , y l − 1 ] + k ; ) 三维空间 : S u m [ i ∈ 范围[l, r] ] + k  ⇔ ( S u m [ x r , y r , z r ] + k ; S u m [ x l − 1 , y r , z r ] − k ; S u m [ x r , y l − 1 , z r ] − k ; S u m [ x r , y r , z l − 1 ] − k ; S u m [ x l − 1 , y l − 1 , z r ] + k ; S u m [ x l − 1 , y r , z l − 1 ] + k ; S u m [ x r , y l − 1 , z l − 1 ] + k ; S u m [ x l − 1 , y l − 1 , z l − 1 ] − k ; 其中的`+ k`表示累加k \\

    {一维空间:Sum[i∈范围[l, r] ] + k ⇔(Sum[xr]+k;Sum[xl−1]−k;)二维空间:Sum[i∈范围[l, r] ] + k ⇔(Sum[xr,yr]+k;Sum[xl−1,yr]−k;Sum[xr,yl−1]−k;Sum[xl−1,yl−1]+k;)三维空间:Sum[i∈范围[l, r] ] + k ⇔(Sum[xr,yr,zr]+k;Sum[xl−1,yr,zr]−k;Sum[xr,yl−1,zr]−k;Sum[xr,yr,zl−1]−k;Sum[xl−1,yl−1,zr]+k;Sum[xl−1,yr,zl−1]+k;Sum[xr,yl−1,zl−1]+k;Sum[xl−1,yl−1,zl−1]−k;" role="presentation" style="position: relative;">{一维空间:Sum[i∈范围[l, r] ] + k ⇔(Sum[xr]+k;Sum[xl−1]−k;)二维空间:Sum[i∈范围[l, r] ] + k ⇔(Sum[xr,yr]+k;Sum[xl−1,yr]−k;Sum[xr,yl−1]−k;Sum[xl−1,yl−1]+k;)三维空间:Sum[i∈范围[l, r] ] + k ⇔(Sum[xr,yr,zr]+k;Sum[xl−1,yr,zr]−k;Sum[xr,yl−1,zr]−k;Sum[xr,yr,zl−1]−k;Sum[xl−1,yl−1,zr]+k;Sum[xl−1,yr,zl−1]+k;Sum[xr,yl−1,zl−1]+k;Sum[xl−1,yl−1,zl−1]−k;
    其中的‘+k‘表示累加k⎩ ⎨ ⎧​一维空间:Sum[i∈范围[l, r] ] + k ⇔(Sum[xr]+k;Sum[xl−1]−k;)二维空间:Sum[i∈范围[l, r] ] + k ⇔(Sum[xr,yr]+k;Sum[xl−1,yr]−k;Sum[xr,yl−1]−k;Sum[xl−1,yl−1]+k;)三维空间:Sum[i∈范围[l, r] ] + k ⇔(Sum[xr,yr,zr]+k;Sum[xl−1,yr,zr]−k;Sum[xr,yl−1,zr]−k;Sum[xr,yr,zl−1]−k;Sum[xl−1,yl−1,zr]+k;Sum[xl−1,yr,zl−1]+k;Sum[xr,yl−1,zl−1]+k;Sum[xl−1,yl−1,zl−1]−k;​
    公式中涉及到(下标越界)的地方, 需以0来替代

    构造

    以临界点为起点 的差分公式:
    { 一维空间 : D i f f [ x ] = S u m [ x ] − S u m [ x + 1 ] 二维空间 : D i f f [ x ] [ y ] = S u m [ x ] [ y ] − S u m [ x + 1 ] [ y ] − S u m [ x ] [ y + 1 ] + S u m [ x + 1 ] [ y + 1 ] 三维空间 : D i f f [ x ] [ y ] [ z ] = S u m [ x ] [ y ] [ z ] − S u m [ x + 1 ] [ y ] [ z ] − S u m [ x ] [ y + 1 ] [ z ] − S u m [ x ] [ y ] [ z + 1 ] + S u m [ x + 1 ] [ y + 1 ] [ z ] + S u m [ x + 1 ] [ y ] [ z + 1 ] + S u m [ x ] [ y + 1 ] [ z + 1 ] − S u m [ x + 1 ] [ y + 1 ] [ z + 1 ] 下标越界处 , 视为 0

    {一维空间:Diff[x]=Sum[x]−Sum[x+1]二维空间:Diff[x][y]=Sum[x][y]−Sum[x+1][y]−Sum[x][y+1]+Sum[x+1][y+1]三维空间:Diff[x][y][z]=Sum[x][y][z]−Sum[x+1][y][z]−Sum[x][y+1][z]−Sum[x][y][z+1]+Sum[x+1][y+1][z]+Sum[x+1][y][z+1]+Sum[x][y+1][z+1]−Sum[x+1][y+1][z+1]" role="presentation" style="position: relative;">{一维空间:Diff[x]=Sum[x]−Sum[x+1]二维空间:Diff[x][y]=Sum[x][y]−Sum[x+1][y]−Sum[x][y+1]+Sum[x+1][y+1]三维空间:Diff[x][y][z]=Sum[x][y][z]−Sum[x+1][y][z]−Sum[x][y+1][z]−Sum[x][y][z+1]+Sum[x+1][y+1][z]+Sum[x+1][y][z+1]+Sum[x][y+1][z+1]−Sum[x+1][y+1][z+1]
    \\ \quad 下标越界处, 视为0 ⎩ ⎨ ⎧​一维空间:Diff[x]=Sum[x]−Sum[x+1]二维空间:Diff[x][y]=Sum[x][y]−Sum[x+1][y]−Sum[x][y+1]+Sum[x+1][y+1]三维空间:Diff[x][y][z]=Sum[x][y][z]−Sum[x+1][y][z]−Sum[x][y+1][z]−Sum[x][y][z+1]+Sum[x+1][y+1][z]+Sum[x+1][y][z+1]+Sum[x][y+1][z+1]−Sum[x+1][y+1][z+1]​下标越界处,视为0

    共2^N项, (N为维度), 且+1 和 0 选与不选.

    经验谈

    • 如果A原数组 均为 0, 则 对差分的 构造, 可以直接:
      … memset( Diff, 0, sizeof( Diff)), 简单又高效.
      当然, 如果A原数组均为相等的 (比如均为x), 则对差分的 构造, 可以:
      … memset( Diff, 0, sizeof( Diff)), Diff[ 起点] = x

    • 前缀和 的 2个操作:
      … (1, 根据A数组 来构造出 Sum数组)
      … (2, 访问Sum数组)
      差分的 3个操作:
      … (1, 根据A数组 来 构造出 Diff数组)
      … (2, 修改Diff数组)
      … (3, 根据Diff数组 恢复 得到 B数组)
      因此, 差分 比 前缀和, 多一个 恢复操作

    • 从原数组A, 得到其: 前缀和Sum数组 和 差分Diff数组,
      最好都新开Sum 和 DIff数组, 最好不要在原数组A的基础上, 去将A修改为 前缀和/差分数组.
      虽然是可以做到的, 但最好还是分开.

    • 从A 得到 前缀和Sum数组, 最好 将 (原点) 作为 (起点)
      即Sum[ i]表示 A[ 0, 1, 2, ..., i] 这个范围

    从A 得到 差分Diff数组, 最好 将 (临界点) 作为 (起点)
    这样, Diff[ i] 也表示 A[ 0, 1, 2, .., i] 这个范围

    越界判断代码

    由于前缀和与差分, 不管是构造还是查询时, 都会涉及到下标越界.
    而下标越界时, 都是按照0处理, 所以, 为了避免特判, 有以下代码:

    int & A_at( int _x, int _y){
    static int Error;
    if( IS_IN_RANGE_( _x, 0, N-1) && IS_IN_RANGE_( _y, 0, M-1)){
        return A[ _x][ _y];
    }
    return Error = 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    例题

    • https://blog.csdn.net/weixin_42712593/article/details/125991596
      二维前缀和与差分的结合

    树上前缀和与差分

    树上前缀和

    查询 两个ab的 简单路径 上, 所有 (边/点) 的权值之和.

    做法1: 倍增
    因为求的是简单路径, 而树上的简单路径可以拆分为: a - lca 和 lca - b, 这两段路径
    在倍增lca算法中, a会跳到lca的儿子, 也就是a - lca这个路径, 我们会扫描到. 同理b - lca路径也会扫描到
    … 因此, 类似于Fa[ N][ 20], 我们也设置一个Sum[ N][ 20], 其中Sum[ x][ k]表示:
    … x 到 Fa[ x][ k] 两点的简单路径上: 所有(点/边)的权值和, 这样在 ab跳到 lca的儿子的过程中, 一步步的累加Sum
    比如, ab简单路径的和 为ans, 则ans = 若干个Sum之和

    这是可以做的. 但比较正式官方的算法是: 树上前缀和
    就像是: 求A[l, ..., r]的区间和, 正式的做法是前缀和;
    而当然用倍增也可以 (将r - l拆分为二进制的若干区间, 然后求所有区间和), 但 前缀和是比较正式的做法

    树上前缀和:

    • 如果权值在 点上, 设置Sum[ i]数组, 表示: i点 到 起点 的 所有点的权值和. 规定起点为树根
      这样, ab简单路径上所有点的权值和 ⇔ \Leftrightarrow ⇔ Sum[ a] + Sum[ b] - Sum[ lca] - Sum[ fa( lca)]
      因为Sum[ fa( lca)] = Sum[ lca] - A[ lca], 所有上面公式 也可以不借助fa( lca)这个点 ,但最好不好这样做.
      … 因为, 这是前缀和公式, 最好只涉及Sum, 不要涉及到A原数组.
      … 而且, fa( lca)不难求, 在求出lca后, Fa[ lca][ 0]便是他的父节点 (根节点需要特判)

    • 如果权值在 边上, (这里的处理很重要), 则将边权 先对应到 点上
      因为树的结构, 每个点 (只有1个父节点 即1个入边, 而有多个子节点 即多个出边)
      我们让一个点, 去代表 他的入边, 因为他的入边是唯一的
      对于这N-1条无向边, 比如一条无向边是a - b, 边权为w, 且depth[ a] = depth[ b] + 1
      … 则, 令A[ a] = w;
      此时, 就转换为: 上面的 (权值在点上)的问题, 再针对A数组, 构建其前缀和Sum数组 (起点在原点)
      … 以A建立(起点为树根)的前缀和Sum, 则Sum[ i]表示: i到树根 的简单路径上 所有边的权值和
      ab简单路径上所有边的权值和 ⇔ \Leftrightarrow ⇔ Sum[ a] + Sum[ b] - 2*Sum[ lca]
      这里非常巧妙, 可以动手画图模拟下
      … 注意点: 并不是说边权就不用存储在Wth[ N * 2]里, 还是需要存的!
      … 因为, 在刚录入a, b, w时, 你并不知道, a b哪个是 深度更大的点! 只有在整个树建立之后, 才能进行遍历.

    代码

    由于(权值在边上), 我们也是将其转换为 (在点上),
    所以, 权值在点/边 的树上前缀和, 代码几乎是一样的

    void Dfs_sum(PAR_(int, _cur), PAR_(int, _fa)) {
    for (int nex, i = Head[ _cur]; ~i; i = Nex[ i]) {
        nex = Ver[ i];
        if (nex != _fa) {
            Sum[ nex] = Sum[ _cur]; //< 不是 `Sum[ _fa]`
            Sum[ nex] += A[ nex] 或 Wth[ i]; //< 权在点为A[ nex], 权在边为Wth[ i]
            Dfs_sum(nex, _cur);
//            DEBUG_(nex, Sum[ nex], Wth[ i]); //<   每一步都调试下
        }
    }
}
void Build_sum() {
    Sum[ Root_] = 0;
    Dfs_sum(Root_, -1);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    例题

    • https://blog.csdn.net/weixin_42712593/article/details/126032274
      树上对(边)的前缀和

    • https://blog.csdn.net/weixin_42712593/article/details/126032640
      树上对(点)的前缀和

    树上差分

    修改ab两点的 简单路径 上的所有(点/边) 的权值. (即, 统一执行+= k操作)

    因为, 树上的边权可以放到 (深度深的端点)上, 即, 对于 (边权问题) 可以转换为 (点权问题)

    即: 修改ab两点的 简单路径 上的所有点的权值. (即, 统一执行+= k操作)

    这里树上差分 和 空间差分一样, 如果我们将: (起点) 和 前缀和一样, 确定为 (树根)
    则, Diff[ i] += k会影响所有的: i点 到 (终点), 也就是 影响整个 (以i为根的子树)
    而且i点的分支 (即他的儿子), 是非常多的
    … 比如要ab的简单路径 += k, 则Diff[ lca] += k肯定要执行这个操作 (因为ab简单路径包含在其中)
    … 但是, Diff[ lca]不仅包含这个ab简单路径, lca不仅两个儿子, 还有很多, 你需要对他的所有 (除了这两个儿子外), 都执行Diff[ i] -= k
    … 你可以动手模拟下, 这是很复杂的. 时间远不是O(1)了.

    而如果我们将 (起点) 放到 (叶子节点)上, 则恰好相反, Diff[ i]影响的是: i到树根的 简单路径, 这就简单很多.

    • 树上节点的原权值为: A[], 其差分为Diff[]
    • 构造Diff ⇔ \Leftrightarrow ⇔ D i f f [ i ] = A [ i ] − ∑ j ∈ s o n ( i ) A [ j ] Diff[ i] = A[ i] - \sum_{j \in son( i)} {A[ j]} Diff[i]=A[i]−∑j∈son(i)​A[j]
      这样, A[ i]的值为: 以i为树根的 整个子树的 所有Diff之和
    • 执行ab简单路径所有点/边都+= k ⇔ \Leftrightarrow ⇔
      1, 如果针对点权, D i f f [ a ] + k , D i f f [ b ] + k , D i f f [ l c a ] − k , D i f f [ f a ( l c a ) ] − k Diff[ a] + k, Diff[ b] + k, Diff[ lca] - k, Diff[ fa( lca)] - k Diff[a]+k,Diff[b]+k,Diff[lca]−k,Diff[fa(lca)]−k
      2, 如果针对边权, D i f f [ a ] + k , D i f f [ b ] + k , D i f f [ l c a ] − 2 ∗ k Diff[ a] + k, Diff[ b] + k, Diff[ lca] - 2*k Diff[a]+k,Diff[b]+k,Diff[lca]−2∗k
    • 恢复 (将Diff恢复为A): A [ i ] = ∑ j ∈ 以 i 为树根的子树所有节点 D i f f [ j ] A[ i] = \sum_{j \in 以i为树根的子树所有节点}{Diff[ j]} A[i]=∑j∈以i为树根的子树所有节点​Diff[j]
      但这个定义式, 不是O(1)的; 因此, 他有一个 递推式, 是O(1)的
      A [ i ] = D i f f [ i ] + ∑ j ∈ s o n ( i ) A [ j ] A[ i] = Diff[ i] + \sum_{j \in son( i)}{A[ j]} A[i]=Diff[i]+∑j∈son(i)​A[j]
    • 如果a == b, 比如, 将a点 += k, 即 单点修改
      为: Diff[ a] += k Diff[ Fa( a)] -= k (如果a为树根, 则Fa( a)不存在, 要特判)

    代码

    以下A[ i], 在(点权问题)中, 表示 该点的权值.
    而在(边权问题)中, 表示 该点入边的权值 (将A[ i]改为 Wth边权)

    void Dfs_build_diff( PAR_( int, _cur), PAR_( int, _fa)){
    Diff[ _cur] = A[ _cur];
    for( int nex, i = Head[ _cur]; ~i; i = Nex[ i]){
        nex = Ver[ i];
        if( nex != _fa){
            Diff[ _cur] -= A[ nex];
            //--
            Dfs_build_diff( nex, _cur);
        }
    }
}
void Build_diff(){
    Dfs_build_diff( Root_, -1);
}
void Dfs_restore_diff( PAR_( int, _cur), PAR_( int, _fa)){
    A[ _cur] = Diff[ _cur];
    for( int nex, i = Head[ _cur]; ~i; i = Nex[ i]){
        nex = Ver[ i];
        if( nex != _fa){
            Dfs_restore_diff( nex, _cur);
            A[ _cur] += A[ nex];
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    例题

    • https://blog.csdn.net/weixin_42712593/article/details/126039291
      针对点的 差分

    • https://blog.csdn.net/weixin_42712593/article/details/126059766
      针对边的 前缀和与差分

    经验谈

    • 对于空间前缀和/差分, 其原点是唯一的, 临界点也是唯一的.
      即, 起点和终点, 也是唯一的.
      而对于树上前缀和/差分, 其原点(树根) 是唯一的, 但是临界点 (也就是叶子节点) 是有很多个的!
      因此, 树上前缀和/差分 的 (起点 或 终点 取决于你的选择), 如果对应临界点, 则不是唯一的.

    • 空间前缀和/差分 的 范围 必须是: 区间, 矩形, 矩阵
      而树上前缀和/差分 的 范围 必须是: 两点间的简单路径

    • 树上前缀和/差分, 都是只针对 点 来操作的!!! Sum[] 或 Diff[] 都是表示的 点
      因此, 对于针对边权的简单路径, 你必须将 边权 映射到 点上, 而且保证他是合理的

  • 相关阅读:
    入门【网络安全/黑客】启蒙教程
    C/C++运算符超详细讲解（系统性学习day5）
    C语言——内存函数
    QT学习管理系统
    最重要的传输层
    系统学习SpringFramework：Spring AOP
    SpringBoot 配置
    CMS，CDN，WAF指纹识别
    Linux：多线程中的互斥与同步
    网络编程 socket函数参数介绍
  • 原文地址：https://blog.csdn.net/weixin_42712593/article/details/125996683