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