XP04-02 DAY03
2025-08-04 21:01:07
发布于：上海
今日主要学习了树状数组这个高级数据结构和单调栈这个算法。
并且还加深了对状态压缩DP的理解,重新梳理了DP的体系。
一.树状数组
树状数组是利用数的二进制特征进行检索的一种树状结构（但其实是以数组的形式呈现出来）。
树状数组主要的作用是高效地查询和维护动态前缀和（或区间和）。
其思路大概是二分法或分治法。
其经典应用有：区间修改+单点查询，区间修改+区间查询，二维区间修改+区间查询，区间最值。
涉及了三个数组：tree[](树状数组）,sum[]（数列A的前缀和数组）,a[]（数列A）。
它们的关系大概是这样的：
，，，，
。
，，......
求的过程其实是每次去掉二进制最后的1。
例如：。
的求法要参考这幅图：
标有数字的圆圈，表示。
（1,3,5,7是的同时也是）。
这幅图可以更直观地体现和的关系。
的父节点会将加上，父节点的父节点也会将加上。
那么的父节点怎么求？
来一个例子：比如这一串数字：1 2 4 8
它们的二进制是 1 10 100 1000。
再比如说这一串：5 6 8。
它们的二进制是101 110 1000。
发现规律：的父节点的二进制的最后一个一比的二进制的最后一个1靠前。
且在的二进制的最后一个1上加1就会是的父节点的二进制。
既然是动态前缀和，更新了，那么与它有关的它的父节点，和它父节点的父节点，就都需要更改。
那么现在最主要的问题是：如何找到的最后一个二进制？
答：使用一个神奇的lowbit()函数（这是要自己写的，并非C++自带）。
大概是这样：
int lowbit(int x){
return x&-x;
}
这是使用了二进制补码的特性，在此不过多进行解释。
模板：（单点修改+区间和）(使用前缀和）：链接描述
#include<bits/stdc++.h>
using namespace std;
const int N=5e5;
int n,m,s,y,z;
int a[N],c[N];
int lowbit(int x){
return x&-x;
}
void add(int x,int pos){
for(;x<=n;x+=lowbit(x))c[x]+=pos;
}
int sum(int x){
int ans=0;
for(;x>0;x-=lowbit(x))ans+=c[x];
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
add(i,a[i]);
}
for(int i=1;i<=m;i++){
cin>>s>>y>>z;
if(s==1)add(y,z);
else cout<<sum(z)-sum(y-1)<<'\n';
}
return 0;
}
模板：（区间修改+单点值）（使用差分）：链接描述
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,s;
int a[N],d[N],c[N];
int lowbit(int x){
return x&-x;
}
void add(int x,int pos){
for(;x<=n;x+=lowbit(x))c[x]+=pos;
}
int sum(int x){
int ans=0;
for(;x>0;x-=lowbit(x))ans+=c[x];
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
d[i]=a[i]-a[i-1];
add(i,d[i]);
}
for(int i=1;i<=m;i++){
cin>>s;
if(s==1){
int y,z,k;
cin>>y>>z>>k;
add(y,k);
add(z+1,-k);
}else{
int y;
cin>>y;
cout<<sum(y)<<'\n';
}
}
return 0;
}
难一点的一道题目：链接描述
这道题很抽象。它涉及到了两个比较难的点。
二.单调栈
比较简单。
单调栈是一种基于栈的算法。
指的是栈中的元素全部都是单调的（即有序）。
用途比较广。
可以求(从左往右/从右往左)第一个(大于/小于) 的数。
题目（模板）：链接描述
#include<bits/stdc++.h>
using namespace std;
int a[300005];
int ans[300005];
stack<int>s;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
while(!s.empty()&&a[s.top()]<a[i]){
ans[s.top()]=i;
s.pop();
}
s.push(i);
}
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
return 0;
}
一个神秘题目：链接描述
三.状态压缩DP
题目：链接描述
这道题还挺有意思的（但是题目描述不太清楚）。
一眼望去，似乎是最短路的样子，但是会先发现,不太对。
再仔细一想，它没有规定来回的顺序，所以不能有DIJ。
DFS要进行记忆化，由此想到DP。
然后就是这道题的模糊点：每个村子除了点一只能经过一次。（点一除了初始在哪里，还需要按照题目要求在最后回来）。
其次就是它的初始化了。需要这样的一句dp[0][1<<0]=0;即可，不能再随意乱加。
#include<bits/stdc++.h>
using namespace std;
int dis[25][25];
int dp[25][1<<20];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>dis[i][j];
}
}
for(int i=0;i<1<<n;i++){
for(int j=0;j<n;j++){
dp[j][i]=1e9;
}
}
for(int i=0;i<n;i++)dp[i][(1<<i)|1]=dis[0][i];
dp[0][1<<0]=0;
for(int sta=1;sta<1<<n;sta++){
for(int i=0;i<n;i++){
if(sta>>i&1){
for(int j=0;j<n;j++){
if(sta>>j&1)continue;
dp[j][sta|(1<<j)]=min(dp[j][sta|(1<<j)],dp[i][sta]+dis[i][j]);
}
}
}
}
int ans=1e9;
for(int i=0;i<n;i++){
ans=min(dp[i][(1<<n)-1]+dis[i][0],ans);
}
cout<<ans;
return 0;
}
四.DP体系的重整
动态规划主要用来做什么题目：
1.求最值 （比如说采药，疯狂的采药，最值问题，方格取数，登山等）。
2.求方案数（比如说不同的路径）。
3，可行性问题（比较少，没找到）。
遇到最值问题的其他解决方案（DP是最坏选择，事实上很多问题都有很多种不同的解法，选择最擅长的即可）：
二分答案，贪心，枚举，深度优先搜索，广度优先搜索，最短路。
写动态规划的几个部分：
1.定义状态
2.初始化状态
3.写状态转移方程
4.确定循环顺序
5.输出答案
定义状态的小技巧：
1.基本上都有一维跟数组下标有关
2.题目要求什么，我的DP状态设成什么（根据答案设计状态）。
3.寻找对应的DP模型。
几个DP模型
1.朴素型：当前的状态只会由前几个状态转移过来。
状态定义：表示第个位置的最值/方案数/可行性是多少
对应状态转移方程：
这类题的代表有爬楼梯等问题。
2.跳跃型：当前的状态不能直接由前面的转移，会有转移限制的问题。
状态定义：表示以结尾的最值/方案数是多少。
对应状态转移方程：
代表问题有最长上升子序列。
3.朴素型+资源分配型
（其实资源分配类型就是背包）。
状态定义：表示在有个物品，背包容量维是的最大价值（其实这类问题还有一维定义，即将舍去）。
状态转移方程：
4.朴素型+区间型
状态定义：表示区间是时能获得的最大价值。
状态转移：枚举断点
循环顺序：先去枚举区间长度，再去枚举开始位置。
代表问题：石子合并，能量项链。
5.朴素型+双序列
状态定义：表示第一个字符串到,第二个字符串到匹配到的最大价值。
这种问题有两种状态转移方程：
第一种：
第二种：
经典问题：最长公共子序列，编辑距离（不太记得了，记得重新过一次）
6.跳跃型+状态压缩
状态定义：表示当前状态是,以结尾的最大值。
状态转移方程：需要满足不在中，并且在中。
经典问题：吃奶酪
这里空空如也
有帮助，赞一个