今日主要学习了树状数组这个高级数据结构和单调栈这个算法。
并且还加深了对状态压缩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;即可，不能再随意乱加。
