Segment Tree

aba aba aba

线段树

啥是线段树嘞？

咱先字面了解一下，线段树就是每个结点是一个线段的树，线段的本质可以理解为序列的区间。最常见的是数列序列。哦对，线段树是一棵二叉树。

线段树有啥好嘞？

线段树一共有三个长处。

1. 线段树的树高是 级别。
2. 对于原始序列的任意一个子区间，都可以在线段树上找到数量在 级别且互不相交的区间的并。不超过 个节点：因为每一层最多选两个节点。
3. 总的节点个数为

模板题一

洛谷

给一个数组，有以下操作

1. 给 和 ，
2. 给 和 ，询问

分解代码

树的节点

struct node{
  int ls, rs; //左右儿子编号
  ll sum; //该节点代表的区间的区间和
}c[N << 1];

更新当前节点区间和

inline void pushup(int rt) {
    c[rt].sum = c[c[rt].ls].sum + c[c[rt].rs].sum;
}

建树

inline int newn(){
    return ++tot; //从节点池里拿出来一个编号为 ++tot 的点（从 1 开始
}

void build(int &rt, int l, int r){ //因为需要修改 rt 的真实值，所以传引用
    if (rt == 0) rt = newn(); //rt == 0 说明当前需要从节点池里拿一个使用
    if (l == r) {c[rt].sum = a[l]; return;} //叶子节点
    build(c[rt].ls, l, mid); //建左树
    build(c[rt].rs, mid + 1, r); //建右树
    pushup(rt); //更新
}

解决操作一

void upd(int rt, int l, int r, int x, int y) {
    if (l == r) {c[rt].sum += y; return;} //因为我们只会往包含 x 的区间走，所以只需要判断 l == r，不需要 l == x && r == x
    if (x <= mid) upd(c[rt].ls, l, mid, x, y); //x 在左边
    else upd(c[rt].rs, mid + 1, r, x, y); //x 在右边
    pushup(rt); //更新
}

解决操作二

ll query(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) return c[rt].sum; //当前节点的区间被完全包含在询问区间里，所以当前区间的贡献就是当前区间的区间和
    ll ans = 0; //记录当前节点的贡献
    if (L <= mid) ans += query(c[rt].ls, l, mid, L, R); //左儿子的贡献
    if (R > mid) ans += query(c[rt].rs, mid + 1, r, L, R); //右儿子的贡献
    return ans;
}

完整的树

#include<bits/stdc++.h>
using namespace std;
#define N 500007
#define mid ((l + r) >> 1)
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

struct node{
  int ls, rs;
  ll sum;
}c[N << 1];

int tot, rot, a[N];

inline int newn(){
    return ++tot;
}

inline void pushup(int rt) {
    c[rt].sum = c[c[rt].ls].sum + c[c[rt].rs].sum;
}

void build(int &rt, int l, int r){
    if (rt == 0) rt = newn();
    if (l == r) {c[rt].sum = a[l]; return;}
    build(c[rt].ls, l, mid);
    build(c[rt].rs, mid + 1, r);
    pushup(rt);
}

void upd(int rt, int l, int r, int x, int y) {
    if (l == r) {c[rt].sum += y; return;}
    if (x <= mid) upd(c[rt].ls, l, mid, x, y);
    else upd(c[rt].rs, mid + 1, r, x, y);
    pushup(rt);
}

ll query(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) return c[rt].sum;
    ll ans = 0;
    if (L <= mid) ans += query(c[rt].ls, l, mid, L, R);
    if (R > mid) ans += query(c[rt].rs, mid + 1, r, L, R);
    return ans;
}

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i) a[i] = rd();
    build(rot, 1, n);
    for (int i = 1; i <= m; ++i) {
        int t = rd();
        if (t == 1) {
            int x = rd(), y = rd();
            upd(rot, 1, n, x, y);
        }
        else {
            int l = rd(), r = rd();
            printf("%lld\n", query(rot, 1, n, l, r));
        }
    }
    return 0;
}

位移线段树

总结点数为

构造

void pushup(int rt) {
    SegTree[rt].val = SegTree[rt << 1].val + SegTree[rt << 1 | 1].val;
}
void build(int l, int r, int rt) {
    if (l == r) {
        SegTree[rt].val = a[l];
        return;
    }
    //SegTree[rt].lazy = 0;
    int m = (l + r) / 2;
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    pushup(rt);
}

单点更新

void update(int pos, int val, int l, int r, int rt) {
    if (l == r) {
        c[rt].val += val;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) update(pos, val, l, m, rt << 1);
    else update(pos, val, m + 1, r, rt << 1 | 1);
    pushup(rt);
}

区间更新

ll query(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) return c[rt].sum;
    ll ans = 0;
    int mid = (l + r) >> 1;
    //pushdown(rt, m - l + 1, r - m);
    if (L <= mid) ans += query(c[rt].ls, l, mid, L, R);
    if (R > mid) ans += query(c[rt].rs, mid + 1, r, L, R);
    return ans;
}

延迟标记

struct node {
  int val, lazy;  
};

区间更新2

void update(int rt, int l, int r, int L, int R, int val) {
    if (L <= l && r <= R) {
        SegTree[rt].val += val * (r - l + 1);
        SegTree[rt].lazy += val;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(rt, m - l + 1, r - m);
    if (L <= mid) update(c[rt].ls, l, mid, L, R, val);
    if (R > mid) update(c[rt].rs, mid + 1, r, L, R, val);
    pushup(rt);
}

void pushdown(int rt, int ln, int rn) {//ln 左二子区间长度 rn 右儿子区间长度
    if (SegTree[rt].lazy) {
        SegTree[rt << 1].lazy += SegTree[rt].lazy;
        SegTree[rt << 1 | 1].lazy += SegTree[rt].lazy;
        SegTree[rt << 1].val += SegTree[rt].lazy * ln;
        SegTree[rt << 1 | 1].val += SegTree[rt].lazy * rn;
        
        SegTree[rt].lazy = 0;
    }
}

延迟标记完整版

struct node{
  int ls, rs;
  ll lazy, sum;
}c[N << 1];

int totnode, rot, a[N], p;

inline int newn(){
    return ++totnode;
}

inline void pushup(int rt) {
    c[rt].sum = (c[c[rt].ls].sum + c[c[rt].rs].sum) % p;
}

void build(int &rt, int l, int r){
    if (rt == 0) rt = newn();
    if (l == r) {c[rt].sum = a[ran[l]]; return;}
    int mid = (l + r) >> 1;
    build(c[rt].ls, l, mid);
    build(c[rt].rs, mid + 1, r);
    pushup(rt);
}

void pushdown(int rt, int ln, int rn) {//ln 左二子区间长度 rn 右儿子区间长度
    if (c[rt].lazy) {
        c[c[rt].ls].lazy = (c[c[rt].ls].lazy + c[rt].lazy) % p;
        c[c[rt].rs].lazy = (c[c[rt].rs].lazy + c[rt].lazy) % p;
        c[c[rt].ls].sum = (c[c[rt].ls].sum + c[rt].lazy * ln % p) % p;
        c[c[rt].rs].sum = (c[c[rt].rs].sum + c[rt].lazy * rn % p) % p;
        
        c[rt].lazy = 0;
    }
}

void update(int rt, int l, int r, int L, int R, int val) {
    if (L <= l && r <= R) {
        c[rt].sum = (c[rt].sum + val * (r - l + 1)) % p;
        c[rt].lazy = (c[rt].lazy  + val) % p;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(rt, mid - l + 1, r - mid);
    if (L <= mid) update(c[rt].ls, l, mid, L, R, val);
    if (R > mid) update(c[rt].rs, mid + 1, r, L, R, val);
    pushup(rt);
}

inline ll query(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) return c[rt].sum;
    ll ans = 0;
    int mid = (l + r) >> 1;
    pushdown(rt, mid - l + 1, r - mid);
    if (L <= mid) ans = (ans + query(c[rt].ls, l, mid, L, R)) % p;
    if (R > mid) ans = (ans + query(c[rt].rs, mid + 1, r, L, R)) % p;
    return ans;
}