天津建站服务,做调查赚钱的网站又哪些,西宁网站开发多少钱,wordpress交互插件文章目录 前缀和算法思想差分算法思想C 版本的前缀和模板一维前缀和二维前缀和 C 版本的差分模板一维差分二维差分 前缀和算法思想
用 O(N) 的复杂度构建前缀和数组#xff0c;通过这种方式达成 O(1) 的时间来得到区间和#xff0c;说是一种算法#xff0c;其实可以说是一种… 文章目录 前缀和算法思想差分算法思想C 版本的前缀和模板一维前缀和二维前缀和 C 版本的差分模板一维差分二维差分 前缀和算法思想
用 O(N) 的复杂度构建前缀和数组通过这种方式达成 O(1) 的时间来得到区间和说是一种算法其实可以说是一种常用的算法思想
差分算法思想
用 O(N) 的复杂度构建差分数组通过这种方式达成 O(1) 的时间让一个区域内的值同时 C
C 版本的前缀和模板
一维前缀和
vectorint v(N), arr(N); // v 是原数组, arr 是前缀数组for (int i 1; i n; i) arr[i] arr[i - 1] v[i];cout arr[r] - arr[l - 1] endl;v 就是题目给出的数组arr 就是我们构建的前缀和数组求一维前缀和的公式就是arr[i] arr[i - 1] v[i]
如果我们要求区间 [ lr ]只需要arr[r] - arr[l - 1]
二维前缀和
vectorvectorint vv(N, vectorint(N)), arr(N, vectorint(N));for (int i 1; i n; i)for (int j 1; j m; j)arr[i][j] vv[i][j] arr[i - 1][j] arr[i][j - 1] - arr[i - 1][j - 1];cout arr[x2][y2] - arr[x1 - 1][y2] - arr[x2][y1 - 1] arr[x1 - 1][y1 - 1] endl;二维前缀和的公式是arr[i][j] vv[i][j] arr[i - 1][j] arr[i][j - 1] - arr[i - 1][j - 1]
记忆方法 把 ij 位置本身vv[i][j]以及上面的前缀和左边的前缀和加在一起再减去他们共同的部分加过两次的部分
如果要求 (x1y1) 到 (x2y2) 这个区间内的值用这个公式arr[x2][y2] - arr[x1 - 1][y2] - arr[x2][y1 - 1] arr[x1 - 1][y1 - 1]
记忆方法 当前区域的前缀和减去一个 x1-1 和一个 y1-1分别配上 y2 和 x2最后加上他们多减去的位置arr[x1-1][y1-1]
PS这次没有 Golang 版本的代码但其实都是一样的开数组然后构建前缀和不同语言没有任何差别这里就摸鱼了
C 版本的差分模板
一维差分
vectorint v(N), arr(N);void insert(int l, int r, int c) {arr[l] c;arr[r 1] - c;
}for (int i 1; i n; i) insert(i, i, v[i]);insert(l, r, c);for (int i 1; i n; i) arr[i] arr[i - 1];insert 函数的操作是让 [lr] 的区间 C
差分数组的性质就是在 l 位置 C原数组 l 及之后的的区间值会全部 C让 r 1 位置 - C就能做到 O(1) 的时间复杂度让原数组的 [lr] 区间全部完成 C 的操作
假设我们对差分数组 [ll] 位置 C那其实就是让原数组的 l 位置 C我们就可以利用这个性质通过 insert 操作通过原数组的值构建差分数组之后还能复用 insert 方法完成区间值的修改
差分数组可以通过求自身的前缀和数组的形式将差分数组转换成原数组也就是arr[i] arr[i - 1]
二维差分
vectorvectorint vv(N, vectorint(N)), arr(N, vectorint(N));void insert(int x1, int y1, int x2, int y2, int c) {arr[x1][y1] c;arr[x2 1][y1] - c;arr[x1][y2 1] - c;arr[x2 1][y2 1] c;
} for (int i 1; i n; i) for (int j 1; j m; j)insert(i, j, i, j, vv[i][j]);insert(x1, y1, x2, y2, c);for (int i 1; i n; i)for (int j 1; j m; j)arr[i][j] arr[i - 1][j] arr[i][j - 1] - arr[i - 1][j - 1];二维差分跟一维也是同理而且他的 insert 计算和前缀和刚好相反比较好记忆二维前缀是分别减去 x1-1y1-1加上 x1y1 都 -1而二维差分是分别减去 x21y21然后加上 x2y2 都 1
