四糸智乃

算法

题解(25)

/ 注册

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

CDQ分治（基于归并排序的分治）

CDQ分治预备知识分治与传统分治相同，CDQ分治的核心思想也是分而治之。对于一个数组序列上的问题，分治的思想是总是考虑中的这一部分，而对于这一求解函数则使用递归表示。式子中的加号并不一定是加法，只表示答案的合并。这个说法有点过于抽象了。 ...

分治 CDQ分治

2020-10-10

25 4418

长链剖分

长链剖分可以视作是dsu on tree算法的一个特例，在学习之前，需要掌握树链剖分以及dsu on tree。 dsu on tree:https://blog.nowcoder.net/n/a84c24c37daf450d8bf9db81607c8f98 dsu on tree用于解...

长链剖分 dsu 启发式合并

2020-04-15

4 2301

dsu on tree（树上启发式合并）

dsu的意思是并查集，但是dsu on tree这个算法和并查集的关系也就剩一个启发式合并了。学习这个算法的切入点还真不在启发式合并，关于启发式合并的问题实际上是最后再考虑它为什么叫启发式合并。我们选什么作为切入点呢，选莫队算法，如果你不懂莫队也没关系，这里只是说这两个算法在应用的场...

dsu 启发式合并

2020-04-15

14 4889

树状数组

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

树状数组前缀和

2020-02-07

4 1658

高维前缀和(SOSDP)

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

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

2020-02-07

27 10259

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

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

树状数组差分前缀和

2020-02-07

9 3350

二维前缀和与差分

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

差分前缀和

2020-02-07

0 1883

前缀和与差分

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

差分前缀和

2020-02-07

16 3491

数位DP

数位DP 所谓数位DP，就是把一个数按照k进制数的每一个位展开，在把每一位的信息作为状态来推出答案。比如：12345这个数在十进制下可拆为1、2、3、4、5，个位可以推十位，十位可以推百位，以此类推。推状态的方法有很多，一般来说第一反应就是像普通dp一样从前往后推，但是由于思维难度较高而...

记忆化搜索数位DP

2020-02-06

7 3723

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

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

离线前缀和

2020-02-06

3 2675