前缀和

定义

前缀和可以简单理解为「数列的前 n 项的和」，可以O(1)地查询区间和，通常在数组不发生更新的情况下使用。

模板

1
2
3
4
int n = arr.length;
int[] preSum = new int[n+1];
for(int i = 0;i < n;++i) preSum[i+1] = preSum[i] + arr[i];	// 预处理前缀和数组
int sumL2R = preSum[r+1] - preSum[l];	// 计算arr[l:r]的和

二维/多维前缀和

二维前缀和定义

设矩阵为mat，二维前缀和数组为preSum，preSum[i][j]的含义可以表述为：从mat[0][0]到mat[i][j]（包含）这一个矩阵的元素总和。

模板

求解二维前缀和可以用容斥原理，如下所示：

1
2
3
4
5
6
7
8
9
10
11
for(int i = 0;i < n;i++){
    for(int j = 0;j < n;j++){
        // 求二维前缀和
        if(j > 0 && i > 0)
            diff[i][j] = diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1] + diff[i][j];
        else if(i > 0)
            diff[i][j] = diff[i-1][j] + diff[i][j];
        else if(j > 0)
            diff[i][j] = diff[i][j-1] + diff[i][j];
    }
}

当维数升高时，这种方法其复杂度较高。可以考虑基于DP的二维/多维前缀和，求法如下：

1
2
for(int i = 0;i < n;++i) for(int j = 1;j < n;++j) diff[i][j] += diff[i][j-1];
for(int i = 1;i < n;++i) for(int j = 0;j < n;++j) diff[i][j] += diff[i-1][j];

树上前缀和

设sumisum_i表示节点ii到根节点的权值总和

  • 若是点权，x,yx,y 路径上的和为sumx+sumy−sumlca−sumfalcasum_x+sum_y-sum_{lca}-sum_{fa_{lca}}，其中最后一项的下标代表最近公共祖先的父亲节点；
  • 若是边权，x,yx,y 路径上的和为sumx+sumy−2∗sumlcasum_x+sum_y-2*sum_{lca}

参考

前缀和 & 差分 - OI Wiki (oi-wiki.org)

__END__