树状数组、线段树与RMQ
树状数组、线段树与RMQ
区间修改问题常用的三种手段，我觉得还是有必要复习一下。
树状数组
binary index tree 来自OI-wiki的图，我记得刘汝佳书里也有，不过那本书不在我手边
树状数组的核心是lowbit：x&(-x)，其中-x为x的负数的补码表示形式，计算出来可以得到x的二进制从右往左的第一个1所对应的十进制数字。 这样就可以算出非叶子节点对应的管辖范围
单点修改，一路上山
int tree[MAXN];
inline void update(int i, int x)
{
for (int pos = i; pos < MAXN; pos += lowbit(pos))
tree[pos] += x;
}求前n项和，一路下山
inline int query(int n)
{
int ans = 0;
for (int pos = n; pos; pos -= lowbit(pos))
ans += tree[pos];
return ans;
}区间查询
inline int query(int a, int b)
{
return query(b) - query(a - 1);
}举个例子，查询前6个的和，lowbit(6) =2 ，所以S[6] = c[6]+c[4]，这是比较自然的。 更新的时候，如果要更新6的话，需要更新c[6]和c[8]的值。 唯一的问题就是需要多加理解，二进制表示毕竟不够直观。但是原题目是很简单的。
RMQ
Range Maximum query，区间查找算法。同样出现在刘汝佳的书里面。该算法的核心是二分法，就是将对一个区间的查找转变为对不断二分的子区间的查找，其中子区间长度均为2的倍数。
因为找不到书了，参考网上的代码
建立
假设有一个数组：1,2,6,8,4,3,7 设二维数组dp[i][j]表示从第i位开始连续2^j个数中的最小值。例如dp[2][1]表示第二位数开始连续两个数的最小值，也就是第二位数和第三位数的最小值，即2. 在求的时候可以将其分为两个部分，第一部分是i到i+2^{j-1}-1，第二部分是i+2^{j-1}到i+2^{j}-1。
显然初始值dp[i][0]为数本身，因此转移方程还是比较好求的 dp[i][j] = min(dp [i][j - 1], dp [i + (1 << j - 1)][j - 1])，也即第一部分和第二部分的最小值在求解。
代码
void rmq_init()
{
for(int i=1;i<=N;i++)
dp[i][0]=arr[i];//初始化
for(int j=1;(1<<j)<=N;j++)
for(int i=1;i+(1<<j)-1<=N;i++)
dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}注意循环变量的顺序不可改变。这相当于就是不断增加区间的长度来更新所有的状态。另外第二部分是可以超过数组长度限制的，这不影响最终的结果。
查询
假设需要查询区间[l,r]的最小值，令k=log2(r-l+1)，区间最小值RMQ[l,r] = min(dp[l][k], dp[r - (1 « k) + 1][k]);，即从左边和右边同时开始搜索的最小值。 证明过程就略了，毕竟也不是搞算法的。这里刘汝佳算法竞赛训练指南那幅图比较直观，查询时其实就是从两端伸出了两个块，只要保证2^k大于等于区间的一半，则最小值一定是能算出来的。
线段树
参考资料 特点是能够在O(logN)的时间复杂度内实现单点修改、区间修改、区间查询（区间求和、求区间最大值、求区间最小值等） 求区间最值用线段树，我的理解是在修改操作较多的时候这样会更好一些。毕竟RMQ每次修改后都要更新一遍dp数组，速度其实也不快。
核心思想也是二分法，把大区间分成两个小区间管理，直到区间长度为1为止。区间索引按照完全二叉树，所以位置为x的节点其孩子分别为2x与2x+1
树建立参考
递归方法建立线段树，其中d数组保存着树节点，a数组保存着原始数据
void build(int s, int t, int p) {
// 对 [s,t] 区间建立线段树,当前根的编号为 p
if (s == t) {
d[p] = a[s];
return;
}
int m = (s + t) / 2;
build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
// 递归对左右区间建树
d[p] = d[p * 2] + d[(p * 2) + 1];
}区间查询
以求和为例子，查询区间[3,5]的和，可以用【3,3】+【4,5】来得到最终结果。 示例代码
int getsum(int l, int r, int s, int t, int p) {
// [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号
if (l <= s && t <= r)
return d[p]; // 当前区间为询问区间的子集时直接返回当前区间的和
int m = (s + t) / 2, sum = 0;
if (l <= m) sum += getsum(l, r, s, m, p * 2);
// 如果左儿子代表的区间 [l,m] 与询问区间有交集,则递归查询左儿子
if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
// 如果右儿子代表的区间 [m+1,r] 与询问区间有交集,则递归查询右儿子
return sum;
}区间维护
如果在修改的时候将所有区间内节点进行修改，代价将难以承受。线段树使用的是”懒惰标记“，即在父节点缓存下更改，这样在查询的时候可以直接累加上对应的修改值。
实例代码1
区间求和
void update(int l, int r, int c, int s, int t, int p) {
// [l,r] 为修改区间,c 为被修改的元素的变化量,[s,t] 为当前节点包含的区间,p
// 为当前节点的编号
if (l <= s && t <= r) {
d[p] += (t - s + 1) * c, b[p] += c;
return;
} // 当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
int m = (s + t) / 2;
if (b[p] && s != t) {
// 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
b[p * 2] += b[p], b[p * 2 + 1] += b[p]; // 将标记下传给子节点
b[p] = 0; // 清空当前节点的标记
}
if (l <= m) update(l, r, c, s, m, p * 2);
if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
d[p] = d[p * 2] + d[p * 2 + 1];
}
int getsum(int l, int r, int s, int t, int p) {
// [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p为当前节点的编号
if (l <= s && t <= r) return d[p];
// 当前区间为询问区间的子集时直接返回当前区间的和
int m = (s + t) / 2;
if (b[p]) {
// 如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m),
b[p * 2] += b[p], b[p * 2 + 1] += b[p]; // 将标记下传给子节点
b[p] = 0; // 清空当前节点的标记
}
int sum = 0;
if (l <= m) sum = getsum(l, r, s, m, p * 2);
if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
return sum;
}区间直接修改为某个值而不是加上某个值
void update(int l, int r, int c, int s, int t, int p) {
if (l <= s && t <= r) {
d[p] = (t - s + 1) * c, b[p] = c;
return;
}
int m = (s + t) / 2;
if (b[p]) {
d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m),
b[p * 2] = b[p * 2 + 1] = b[p];
b[p] = 0;
}
if (l <= m) update(l, r, c, s, m, p * 2);
if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
d[p] = d[p * 2] + d[p * 2 + 1];
}
int getsum(int l, int r, int s, int t, int p) {
if (l <= s && t <= r) return d[p];
int m = (s + t) / 2;
if (b[p]) {
d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m),
b[p * 2] = b[p * 2 + 1] = b[p];
b[p] = 0;
}
int sum = 0;
if (l <= m) sum = getsum(l, r, s, m, p * 2);
if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
return sum;
}腾讯云开发者
