kuangbin线段树专题

写在前面的话

博主自己也算是学了一阵子线段树了, 看到kuangbin线段树专题 还没有人进行过系统的整理, 所以自己想做这样的一个专题, 把自己做题的思路和心得分享出来与大家一起交流.

在本文中您发现了错误也请在评论中指出. 如果您有疑惑同样可以评论留言, 我会在看到后即时回复.

如果这篇博客帮助到了您, 这里也希望您能点一个大大的赞?支持博主, 这样也能让这篇博客帮助到更多的人

题解部分(最下方有博主的板子)

做题顺序: 按照下面题单顺序从前往后做即可.

线段树模板

基础线段树

重点: 维护区间的某种属性, 如: 前缀和 最大值 最小值等.

1. pushdown函数 (一般做一个重载) 作用: 由父亲节点维护子节点, 下放懒标记.
   当操作的区间需要分裂时调用. (在modify和ask函数中)
   
   
2. pushup函数 (根据需要选择是否重载)(是否维护多种信息) 作用: 由子节点维护父亲节点.
   当子节点改变时, 需要调用, 以保证父亲节点信息正确
   
   
3. build函数, 建树, 推荐将树中的所有数据都手动进行初始化, 避免可能因多组输入产生的错误
4. modify函数, 修改函数. 在进行区间修改的时候, 区间分裂时不要忘记pushdown, 修改后应pushup
5. ask函数, 询问函数, 当遇到区间合并问题时, 应当返回类型为节点类型.

/* 基础数据结构 */ int w[N]; //初始化的值 struct node { 
    int l, r; //维护区间 ll sum; //维护的属性 ll lazy; //懒标记, 当前节点的懒标记不包括自己. }t[N << 2]; /* 基础函数 */ void pushdown(node& op, ll lazy) { 
    //重载. 作用: 给当前节点加上懒标记 一定写重载!!! op.sum += lazy * (op.r - op.l + 1); //维护当前节点属性 op.lazy += lazy; //累加懒标记 } void pushdown(int x) { 
    if (!t[x].lazy) return; pushdown(t[x << 1], t[x].lazy), pushdown(t[x << 1 | 1], t[x].lazy); t[x].lazy = 0; //节点懒标记清空 } void pushup(node& p, node& l, node& r) { 
    //重载. 作用: 把l, r区间信息合并得到父亲节点p p.b = l.b + r.b; p.d = gcd(l.d, r.d); //涉及到区间合并的时候重载 } void pushup(int x) { 
    pushup(t[x], t[x << 1], t[x << 1 | 1]); } void build(int l, int r, int x = 1) { 
    t[x] = { 
    l, r, w[l], 0... }; //特别注意, 如果有多组的情况, 懒标记一定要赋初值 if (l == r) return; int mid = l + r >> 1; build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1); pushup(x); //不要忘了!!! } void modify(int a, int c, int x = 1) { 
    //单点修改, a为要修改的点, c为修改的值 if (t[x].l == t[x].r /* && t[x].l == a */) { 
    //修改操作, 这里不需要pushup了, 因为递归结束后会pushup return; } int mid = t[x].l + t[x].r >> 1; modify(a, c, x << 1 | (a > mid)); pushup(x); } void modify(int l, int r, int c, int x = 1) { 
    //区间修改 if (l <= t[x].l && r >= t[x].r) { 
    pushdown(t[x], c); //可以认为是对这个节点进行了一次pushdown return; } pushdown(x); //后续pushup需要根据子节点维护父亲节点, 所以要下放懒标记 int mid = t[x].l + t[x].r >> 1; if (l <= mid) modify(l, r, c, x << 1); if (r > mid) modify(l, r, c, x << 1 | 1); pushup(x); } auto ask(int l, int r, int x = 1) { 
    if (l <= t[x].l && r >= t[x].r) { 
    return t[x].sum/*t[x]*/; //若涉及到区间合并, 则返回节点类型 } pushdown(x); int mid = t[x].l + t[x].r >> 1; /* 维护单值情况 ll sum = 0; if (l <= mid) sum += ask(l, r, x << 1); if (r > mid) sum += ask(l, r, x << 1 | 1); return sum; */ /* 涉及到区间合并的情况 */ if (r <= mid) return ask(l, r, x << 1); //仅在左半部分 if (l > mid) return ask(l, r, x << 1 | 1); //仅在右半部分 auto left = ask(l, r, x << 1), right = ask(l, r, x << 1 | 1); //横跨左右, 构造新区间 node res; //注意p是否需要初始化某些值, 有的合并不局限于左右儿子 pushup(res, left, right); //此时要把left和right合并为新的区间  return res; } 

END