预备知识：懒惰标志，就是在二叉树里，a有b c两个子儿子，现在要给b c各加1，先不直接加到b c上，把它俩要加的值先加到a上，待要实际用时a再把值传给他们。
线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。
线段树可以在 o(log n) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
建树，先建总的区间，然后再建它左右子树，它左右子树是其父结点区间的左右各半，到最后叶子结点为自己为止。
注意：下文的s， t是数组最左最右；l， r 是要查的
//建树 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];//d数组是该区间的值 }
查询，按区间左右两半一直搜
//查询区间值 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,s到t内查l到m的这一半 // 如果左儿子代表的区间 [l,m] 与询问区间有交集,则递归查询左儿子 if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);//同上 // 如果右儿子代表的区间 [m+1,r] 与询问区间有交集,则递归查询右儿子 return sum; }
区间修改（区间加上某个值）带懒惰标记 ：
//区间修改 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;//b值为它未传给左右儿子的值，也做懒惰标记用 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];//更新d数组 }
区间查询（区间求和）带懒惰标记：
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; }
题目待续…
0 条评论