Llf's blog

标签 前缀和差分 下的文章

December 25, 2017

前缀和差分

前缀和差分用于在多次求数据中选取一部分的和,可分为一维前缀和和二维前缀和 一维前缀和 运用递推,将数组每一个元素替换为到这个元素的所有元素之和,如 1 3 4 3 2 5 在处理后变为 1 4 8 11 13 18 如何需要求出数组第X位到第Y位的和,直接用f[y]-f[x-1]即可 二维前缀和 与一维前缀和同理,只是f[a][b]的值变为从s[1][1]到这个点的矩阵内所有数的和,如s...