简介

常用来维护区间信息的数据结构，可以在\(Olog(n)\)的时间内实现区间修改，区间信息合并，单点修改。

结构

建树

注意：线段树空间需要开到四倍。

struct Node {
    int minv;
} seg[N * 4];

// 根据左右儿子更新父亲节点信息
void update(int id) {
    seg[id].minv = min(seg[id * 2].minv, seg[id * 2+ 1].minv);
}

// [l, r]
void bulid(int id, int l, int r) {
    if (l == r) {
        seg[id].minv = arr[l];
    } else {
        int mid = (l + r) / 2;
        bulid(id * 2, l, mid);
        bulid(id * 2 + 1, mid + 1, r);
        update(id);
    }
}

多个信息存储和计算

定义一个info操作，简化代码

// 最大子段和 mpre最大前缀 msuf最大后缀 全部
struct info {
    ll mss, mpre, msuf, s;
    // 初始化操作
    info() {}
    info (int a) : mss(a), mpre(a), msuf(a), s(a) {}
};

struct Node {
    info val;
} seg[N * 4];

info operator + (const info &l, const info &r) {
    info res;
    res.mss = max({l.mss, r.mss, l.msuf + r.mpre});
    res.mpre = max(l.mpre, l.s + r.mpre);
    res.msuf = max(r.msuf, r.s + l.msuf);
    res.s = l.s + r.s;
    return res;
}

懒标记

1. 标记下传

   • 清除标记

2. 打标记

   • 标记合并
   • 信息更新

修改操作时,标记只到需要修改的节点就停止，等到查询操作需要用到他们的子节点的时候，才会进行下传到下面的子节点。

在打标记的时候考虑标记有无顺序的要求，如何进行标记合并以及打到信息上。

struct info {
    ll maxv;
};

struct tag {
    ll add;
};

struct Node {
    tag t;
    info val;
} seg[N * 4];

info operator + (const info &l, const info &r) {
    return {max(l.maxv, r.maxv)};
}

info operator + (const info &v, const tag &t) {
    return {v.maxv + t.add};
}

tag operator + (const tag &t1, const tag &t2) {
    return {t1.add + t2.add};
}

// 根据左右儿子更新父亲节点信息
void update(int id) {
    seg[id].val = seg[id * 2].val + seg[id * 2 + 1].val;
}

//  打标记
void settag(int id, tag t) {
    seg[id].val = seg[id].val + t;
    seg[id].t = seg[id].t + t;
}

// 标记下传
void pushdown(int id) {
    //  标记非空
    if (seg[id].t.add != 0) {
        settag(id * 2, seg[id].t);
        settag(id * 2 + 1, seg[id].t);
        seg[id].t.add = 0;
    }
}

// 节点编号 对应区间 修改位置 修改的值
void modify(int id, int l, int r, int ql, int qr, tag t) {
    if (l == ql && r == qr) {
        settag(id, t);
        return;
    } else {
        int mid = (l + r) / 2;
        // 标记下传 !! 
        pushdown(id);
        if (qr <= mid) {
             modify(id * 2, l, mid, ql, qr, t);
        } else if (ql > mid) {
            modify(id * 2 + 1, mid + 1, r, ql, qr, t);
        } else {
            modify(id * 2, l, mid, ql, mid, t);
            modify(id * 2 + 1, mid + 1, r, mid + 1, qr, t);
        }
        update(id);
    }
}

info query(int id, int l, int r, int ql, int qr) {
    if (l == ql && r == qr) {
        return seg[id].val;
    } else {
        int mid = (l + r) / 2;
        // 标记下传
        pushdown(id);
        if (qr <= mid) {
            return query(id * 2, l, mid, ql, qr);
        } else if (ql > mid) {
            return query(id * 2 + 1, mid + 1, r, ql, qr);
        } else {
            return query(id * 2, l, mid, ql, mid) + query(id * 2 + 1, mid + 1, r, mid + 1, qr);
        }
    }
}

单点修改

// 节点编号 对应区间 修改位置 修改的值
void change(int id, int l, int r, int pos, int val) {
    if (l == r) {
        seg[id].minv = val;
    } else {
        int mid = (l + r) / 2;
        if (pos <= mid) {
            change(id * 2, l, mid, pos, val);
        } else {
            change(id * 2 + 1, mid + 1, r, pos, val);
        }
        //!!修改完后记得层层更新回去
        update(id);
    }
}

区间信息查询

int query(int id, int l, int r, int ql, int qr) {
    if (l == ql && r == qr) {
        return seg[id].minv;
    } else {
        int mid = (l + r) / 2;
        if (qr <= mid) {
            return query(id * 2, l, mid, ql, qr);
        } else if (ql > mid) {
            return query(id * 2 + 1, mid + 1, r, ql, qr);
        } else {
            return min(query(id * 2, l, mid, ql, mid), 
            query(id * 2 + 1, mid + 1, r, mid + 1, qr));
        }
    }
}

线段树上二分

int search(int id, int l, int r, int ql, int qr, int d) {
    if (l == ql && r == qr) {
        if (seg[id].val < d) {
            return -1;
        } else {
            int mid = (l + r) / 2;
            if (l == r) {
                return l;
            }
            if (seg[id * 2].val >= d) {
                return search(id * 2, l, mid, ql, mid, d);
            } else {
                return search(id * 2 + 1, mid + 1, r, mid + 1, r, d);
            }
        }
    } else {
        int mid = (l + r) / 2;
        if (qr <= mid) {
            return search(id * 2, l, mid, ql, qr, d);
        } else if (ql > mid) {
            return search(id * 2 + 1, mid + 1, r, ql, qr, d);
        } else {
            int pos = search(id * 2, l, mid, ql, mid, d);
            if (pos == -1) {
                return search(id * 2 + 1, mid + 1, r, mid + 1, qr, d);
            } else {
                return pos;
            }
        }
    }
}