四糸智乃

分类

算法(12) 题解(25)

/ 注册

TA的专栏 0篇文章 0人订阅

算法小入门

0篇文章 0人学习

全部文章（共35篇）

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

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

dsu 启发式合并

2020-04-15

14 4892

树状数组

树状数组树状数组常用于维护前缀信息，如前缀和、前缀乘积等等。最常见的如给你一个长度为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

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

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

多项式卷积差分前缀和

2020-02-06

14 2428

CodeForces 600E Lomsat gelral

树上启发式合并(dsu on tree)，也叫静态树链分治模板题,预处理dfn可以节省一个dfs，改写成for循环，常数更小。 #include<bits/stdc++.h> using namespace std; const int MAXN=100005; int n; int ...

静态树链分治 dsu 启发式合并

2019-07-30

0 895