四糸智乃

算法

题解(25)

/ 注册

全部文章 / 算法（共7篇）

树状数组

树状数组树状数组常用于维护前缀信息，如前缀和、前缀乘积等等。最常见的如给你一个长度为n的数组，单点修改，查询区间的和。首先是想一下为什么不能用前缀和数组强行搞先看一下前缀和黄色和蓝色部分合起来表示前缀和覆盖的区间黄色表示前缀和信息储存的位置 ...

树状数组前缀和

2020-02-07

4 1651

高维前缀和(SOSDP)

高维前缀和(SOSDP) 高维前缀和，又叫SOSDP，Sum over Subsets dynamic programming，它一般是用来解决子集类的求和问题（虽然也可以解决高维空间的求和问题，但是时空往往不允许）。高维度下求前缀和时，时间复杂度的瓶颈先看一下前缀和的式子一...

状态压缩高维前缀和前缀和

2020-02-07

27 10133

树状数组维护前缀和的前缀和

树状数组维护前缀和的前缀和这个东西的用途其实不太大，复杂的区间信息还是靠线段树，而且这个操作线段树能直接干了。主要应用在以下两个方面： 1、区间加数，区间求和问题。 2、区间加等差数列，单点求值问题。 ①可以用线段树直接干，②可以维护差分数组转化为①。虽然在...

树状数组差分前缀和

2020-02-07

9 3303

二维前缀和与差分

二维前缀和与差分对于一个二维数组a定义数组为数组a的前缀和数组，可以理解为一个左上矩阵的矩阵和 //为了避免数组越位，下标从1开始 for(int i=1;i<=n;++i) { for(int j=1;j<...

差分前缀和

2020-02-07

0 1880

前缀和与差分

前缀和与差分对于一个数组a定义数组为a数组的前缀和数组。 //为了避免数组越位，下标从1开始用 for(int i=1;i<=n;++i) { s[i]=s[i-1]+a[i]; } 定义数组...

差分前缀和

2020-02-07

16 3471

静态维护区间加等差数列的求和问题

静态维护区间加等差数列的求和问题维护一个数组，先进行m次操作，然后查询每个位置的值，每个操作给定四个参数l,r,a,k表示从l到r依次加上一个首项为a，公差为k的等差数列。维护数组，表示原数组的二阶差分。修改操作 void add(int l,int&...

离线前缀和

2020-02-06

3 2639

静态维护区间加多项式的求和问题

知识预备多项式差分对于一个多项式函数,定义它在x的一阶向前差分为,定义它在x的一阶向后差分为。定义k阶向前差分：，定义k阶向后差分：，定义0阶差分：多项式差分的性质 (C为常数)；若,为最高次项系数为的n次多...

多项式卷积差分前缀和

2020-02-06

14 2392