线段树学习笔记

sunkuangzheng · 2024-02-25 15:17:32 · 个人记录

推荐在 cnblogs 阅读。

终于学会线段树了！！！

这篇博客将简单介绍 atcoder::lazy_segtree 的使用方法。

segtree 只需要 S,op,e 三个参数，含义相同。

构造

lazy_segtree<S, op, e, F, mapping, composition, id> seg(n);

lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<T> a);

下面所有代码将用 01 序列，区间 \operatorname{XOR} 1 区间求和举例。

线段树节点 S：每个节点维护的信息。

上面的题目要求每个节点维护区间和以及区间长度。

struct S{int sum,len;};

函数 S op(S x,S y)：push_up 函数。

即合并两个线段树节点。

区间和和区间长度都是直接相加。

S op(S l,S r){return S{l.sum + r.sum,l.len + r.len};}

函数 S e()：返回初始值 e。

它要求任意元素 x 和 e 操作后返回值是 x，例如取 \min 时 e = \inf，本题中 e = \{0,0\}。

S e(){return S{0,0};}

操作 F：修改时进行的操作。

本题中 F =0/1 表示区间要异或的值。

using F = bool;

函数 S mapping(F f,S x)：返回元素 x 应用 f 操作后的值。

在本题里，异或 1 后 sum = len-sum，异或 0 则不变。

S mapping(F f,S x){return S{(f ? x.len - x.sum : x.sum),x.len};}

函数 F composition(F f,F g)：操作之间的复合，返回 f(g(x))。

也就是两个 tag 的合并。在本题里，合并两个异或 tag 即把它们异或起来。

F composition(F f,F g){return (F)(f ^ g);}

函数 F id()：该函数应有 f(x) = x。

本题中返回 0 即可。

F id(){return 0;}

完整代码

using namespace atcoder;
int T,n;
struct S{int sum,len;};
using F = bool;
S op(S l,S r){return S{l.sum + r.sum,l.len + r.len};}
S e(){return S{0,0};}
S mapping(F f,S x){return S{(f ? x.len - x.sum : x.sum),x.len};}
F composition(F f,F g){return (F)(f ^ g);}
F id(){return 0;}
vector<S> a; int q;
void los(){
    cin >> n >> q; string s;
    cin >> s,s = " " + s;
    for(int i = 1;i <= n;i ++) a.push_back(S{s[i] - '0',1});
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
    while(q --){
        int po,l,r;
        if(cin >> po >> l >> r,!po) seg.apply(l - 1,r,F(1));
        else cout << seg.prod(l - 1,r).sum << "\n";
    }
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(T = 1;T --;) los();
}

调试技巧和注意事项

由于 ACL 的线段树采用非递归写法，调试难度略高于手写的线段树。有几个调试技巧和注意事项：

ACL 的线段树如果 n 不是 2^k 的形式，会帮你自动补齐。如果你对 n=5 的序列开线段树，那么根的左右儿子是 [1,4],[5,5] 而不是 [1,3],[4,5]。
调试时可以在 S 中加入 l,r 表示区间的左右端点，并在 mapping 函数里输出 l,r 和 F,S。

最近做的线段树题都会使用 atcoder::lazy_segtree，写完以后会把题目和代码贴在这里。

P2574 XOR的艺术

就是上面的例题。

ACLPC L - Lazy Segment Tree

注意到 01 序列的逆序对只能是子序列 10 的数量，线段树维护区间 0,1,10 的数量。

using namespace atcoder;
const int N = 5e5+5;
using namespace std;
int T,n,q,tmp,po,l,r;
struct S{int x,y; ll ans;};
using F = bool;
S op(S l,S r){return S{l.x + r.x,l.y + r.y,l.ans + r.ans + 1ll * l.y * r.x};}
S e(){return S{0,0,0};}
S mapping(F f,S x){return !f ? x : S{x.y,x.x,1ll * x.x * x.y - x.ans};}
F composition(F f,F g){return F(f ^ g);}
F id(){return 0;}
vector<S> a;
void los(){
    cin >> n >> q;
    for(int i = 1;i <= n;i ++) cin >> tmp,a.emplace_back(!tmp,tmp,0);
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
    while(q --){
        if(cin >> po >> l >> r,po == 1) seg.apply(l - 1,r,F(1));
        else cout << seg.prod(l - 1,r).ans << "\n"; 
    }
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(T = 1;T --;) los();
}

[ABC265G] 012 Inversion

给定 012 序列 a，支持区间替换（0 \to x,1 \to y,2 \to z,x,y,z \in \{0,1,2\}）和区间查逆序对。

比较恶心的题。

线段树节点记录 0,1,2,10,20,21 的数量，tag 维护 0,1,2 分别变成谁。修改时，0,1,2 的数量可以直接得到，原本的 10,20,21 直接贡献给 f_1f_0,f_2f_0,f_2f_1，注意 01 也会贡献给 f_0f_1。01 的数量显然是原本的 0 \times 1 - 01。

合并两个 tag f,g 时，只需要返回 f_{g_i}。

#include <atcoder/lazysegtree>
using namespace atcoder;
struct S{
    ll r[6]; 
    ll operator [](int x){return r[x];};
};
struct F{
    int f[3];
    int operator [](int x){return f[x];};
};
S op(S l,S r){
    return S{{l[0] + r[0],l[1] + r[1],l[2] + r[2],
        l[3] + r[3] + l[1] * r[0],l[4] + r[4] + l[2] * r[0],l[5] + r[5] + l[2] * r[1]}};
}S e(){return S{0,0,0,0,0,0};}
S mapping(F f,S x){
    vector<vector<ll>> fk(3,vector<ll>(3)); vector<ll> sb(3);
    fk[f[0]][f[0]] += x[0],fk[f[1]][f[1]] += x[1],fk[f[2]][f[2]] += x[2],
    fk[f[1]][f[0]] += x[3],fk[f[2]][f[0]] += x[4],fk[f[2]][f[1]] += x[5],
    fk[f[0]][f[1]] += x[0] * x[1] - x[3],fk[f[0]][f[2]] += x[0] * x[2] - x[4],
    fk[f[1]][f[2]] += x[1] * x[2] - x[5],sb[f[0]] += x[0],sb[f[1]] += x[1],sb[f[2]] += x[2];
    return S{sb[0],sb[1],sb[2],fk[1][0],fk[2][0],fk[2][1]};
}F composition(F f,F g){
    return F{f[g[0]],f[g[1]],f[g[2]]};
}F id(){return {0,1,2};}
int T,n,q,x,po,l,r,s1,s2,s3;
vector<S> a;
void los(){
    cin >> n >> q;
    for(int i = 1;i <= n;i ++) cin >> x,a.push_back({(x == 0),(x == 1),(x == 2),0,0,0});
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
    while(q --){
        if(cin >> po >> l >> r,po == 1){
            auto s = seg.prod(l - 1,r);
            cout << s.r[3] + s.r[4] + s.r[5] << "\n";
        }else cin >> s1 >> s2 >> s3,seg.apply(l - 1,r,F{s1,s2,s3});
    }
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(T = 1;T --;) los();
}

P4374 [USACO18OPEN] Disruption P

给定 n 个点的树和 m 条带权额外边，问断掉每条树边后使两端连通的最小额外边边权，或报告不存在这样的边。

一条边的贡献是树链取 \min。树剖 + 线段树。

using namespace atcoder;
using S = int;
using F = int;
S op(S l,S r){return min(l,r);}
S e(){return 2e9;}
S mapping(F f,S x){return min(f,x);}
F composition(F f,F g){return min(f,g);}
F id(){return 2e9;}
int m,dfn[N],top[N],fa[N],au[N],av[N],son[N],dep[N],u,v,w,siz[N],tot; vector<int> g[N];
void los(){
    cin >> n >> m;
    for(int i = 1;i < n;i ++) cin >> u >> v,g[u].push_back(v),g[v].push_back(u),au[i] = u,av[i] = v;
    auto dfs1 = [&](auto self,int u,int f) -> void {
        fa[u] = f,siz[u] = 1,dep[u] = dep[f] + 1;
        for(int v : g[u]) if(v != f) if(self(self,v,u),siz[u] += siz[v],siz[v] > siz[son[u]]) son[u] = v;
    };auto dfs2 = [&](auto self,int u,int tp) -> void {
        dfn[u] = ++tot,top[u] = tp; if(son[u]) self(self,son[u],tp);
        for(int v : g[u]) if(v != fa[u] && v != son[u]) self(self,v,v);
    }; dfs1(dfs1,1,0),dfs2(dfs2,1,1);
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(n);
    auto upd = [&](int u,int v){
        while(top[u] != top[v]){
            if(dep[top[u]] < dep[top[v]]) swap(u,v);
            seg.apply(dfn[top[u]] - 1,dfn[u],w),u = fa[top[u]];
        }if(u == v) return ;
        seg.apply(min(dfn[u],dfn[v]),max(dfn[u],dfn[v]),w);
    };
    while(m --)
        cin >> u >> v >> w,upd(u,v);
    for(int i = 1;i < n;i ++){
        int d = (dfn[au[i]] > dfn[av[i]] ? dfn[au[i]] : dfn[av[i]]),ans = seg.prod(d - 1,d);
        cout << (ans > 1e9 ? -1 : ans) << "\n";
    }
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(T = 1;T --;) los();
}

P4314 CPU 监控

线段树历史最值。

const ll inf = -1e18;
struct S{ll v,h;};
struct F{ll cov,add,mx,cmx;};
S op(S a,S b){return S{max(a.v,b.v),max(a.h,b.h)};}
S e(){return S{inf,inf};}
S mp(F f,S x){return S{(f.cov == inf ? x.v + f.add : f.cov),max({x.h,x.v + f.mx,f.cmx})};}
F cp(F f,F g){
    if(f.cov == inf){
        if(g.cov == inf) return F{inf,f.add + g.add,max(g.mx,g.add + f.mx),g.cmx};
        else return F{g.cov + f.add,0,g.mx,max(g.cmx,g.cov + f.mx)};
    }else return F{f.cov,0,(g.cov == inf ? max(g.mx,g.add + f.mx) : g.mx),max({f.cmx,g.cmx,g.cov + f.mx})};
}F id(){return F{inf,0,0,inf};}

参考文献

AClibrary Lazy Segtree 官方文档

像使用stl一样使用线段树——区间修改与实例