跳至主要內容

「笔记」维护区间最大子段和/最大连续子段——Kadane 算法在线段树上的应用

Mohao2025/10/25大约 6 分钟笔记线段树Kadane

「笔记」维护区间最大子段和/最大连续子段——Kadane 算法在线段树上的应用

这是全新品类的博文

感觉最近做过一万道这种[1]原又典的题目，故写一篇笔记记录一下。

Kadane 算法

其实维护最大子段和的算法是有学名的，如题。

本质上是一个动态规划算法，即对于问题：

给定长度为 nn 的数组 AA，求 AA 的连续子段 [l,r][l, r] 使得 ∑ljAi\sum_l^j A_i 最大。当然这里显然有 (∃ i∈[1,n])  Ai<0(\exists~i \in [1, n])~~A_i<0，于是我们不难有 O(n)\mathcal{O}(n) 的解法如下：

定义 fif_i 是以 AiA_i 结尾的最大子段和，有转移方程：

fi=max⁡(Ai,fi−1+Ai)f_i=\max(A_i,f_{i-1}+A_i)

这玩意看起来好像过于显然以至于好像大多数人都不知道这个有名字。

区间问题

然后我们不难拓展到区间上，即在原问题的基础上加上单点修改和区间查询。

然后我们不难想到线段树。

考虑线段树维护的是一个幺半群（英文：Monoid），即是一个带有二元运算 ⋅:M×M→M\cdot:M \times M \to M 的集合 MM，符合以下公理：

  • 结合律：对于所有 a,b,c∈Ma, b, c \in M，有 a⋅(b⋅c)=(a⋅b)⋅ca \cdot(b\cdot c)=(a\cdot b) \cdot c；
  • 单位元：存在 e∈Me \in M，使得任意 a∈Ma\in M，有 a⋅e=e⋅a=aa \cdot e = e \cdot a = a。

然后我们惊人地发现最大子段和正好满足这个条件！即我们考虑两个维护了最大子段和节点信息的合并：

合并后节点的最大子段和，要么是左节点的最大子段和，要么是右节点的最大子段和，要么是横跨左右节点的一段子段和。

然后我们不难发现，横跨左右节点的子段和，就是左节点的最大后缀和拼上右节点的最大前缀和。

于是我们可以用一个四元组 (sum,ans,pre,suf)(\rm{sum}, \rm{ans}, \rm{pre}, \rm{suf}) 来维护这个信息，有合并操作 res=lhs⋅rhs\rm{res} = \rm{lhs} \cdot \rm{rhs} 如下：

res.sum=lhs.sum+rhs.sumres.ans=max⁡(lhs.ans,rhs.ans,lhs.suf+rhs.pre)res.pre=max⁡(lhs.pre,lhs.sum+rhs.pre)res.suf=max⁡(rhs.suf,lhs.suf+rhs.sum)\begin{aligned} &\rm{res.sum}=\rm{lhs.sum}+\rm{rhs.sum} \\ &\rm{res.ans}=\max(\rm{lhs.ans},\rm{rhs.ans},\rm{lhs.suf}+\rm{rhs.pre}) \\ &\rm{res.pre}=\max(\rm{lhs.pre},\rm{lhs.sum}+\rm{rhs.pre}) \\ &\rm{res.suf}=\max(\rm{rhs.suf}, \rm{lhs.suf}+\rm{rhs.sum}) \end{aligned}

然后我们不难定义单位元 e=(0,−∞,−∞,−∞)e=(0,-\infty,-\infty,-\infty)

例题一

洛谷：P4513 小白逛公园

维护若干个区间赋值和区间查询最大子段和操作。

参考实现
#include <bits/stdc++.h>
using namespace std;

template <class S> struct SegTree {
    int n;
    std::vector<S> tree;

    void build(auto &&v, int p, int l, int r) {
        if (l == r) {
            tree[p] = S(v[l]);
            return;
        }
        int mid = l + (r - l) / 2;
        build(v, 2 * p, l, mid);
        build(v, 2 * p + 1, mid + 1, r);
        pull(p);
    }

    void pull(int p) { tree[p] = tree[2 * p] + tree[2 * p + 1]; }

    S query(int ql, int qr, int p, int l, int r) {
        if (r < ql or qr < l)
            return {};
        if (ql <= l and r <= qr)
            return tree[p];
        int mid = l + (r - l) / 2;
        return query(ql, qr, 2 * p, l, mid) + query(ql, qr, 2 * p + 1, mid + 1, r);
    }

    void update(int pos, const S &val, int p, int l, int r) {
        if (l == r) {
            tree[p] = val;
            return;
        }
        int mid = l + (r - l) / 2;
        if (pos <= mid)
            update(pos, val, 2 * p, l, mid);
        else
            update(pos, val, 2 * p + 1, mid + 1, r);
        pull(p);
    }

    SegTree(int n) : n(n), tree(4 * n) {}
    SegTree(auto &&v) : n(v.size()), tree(4 * n) {
        build(v, 1, 0, n - 1);
    }

    S Query(int l, int r) { return query(l, r, 1, 0, n - 1); }
    void Update(int p, const S &v) { update(p, v, 1, 0, n - 1); }
};

using i64 = long long;

// 典中典之 Kadane
struct Kadane {
    i64 len{};
    i64 sum{}, ans = -1e18;
    i64 pre = -1e18, suf = -1e18;

    Kadane() = default;
    Kadane(i64 v) {
        len = 1;
        sum = v;
        pre = v;
        suf = v;
        ans = v;
    }
};

Kadane operator+(const Kadane &l, const Kadane &r) {
    Kadane res{};
    res.len = l.len + r.len;
    res.sum = l.sum + r.sum;
    res.pre = max(l.pre, l.sum + r.pre);
    res.suf = max(r.suf, l.suf + r.sum);
    res.ans = max({l.ans, r.ans, l.suf + r.pre});
    return res;
}

using Seg = SegTree<Kadane>;

signed main() {
    int n, m;
    cin >> n >> m;
    vector<i64> a(n);
    for (auto &x : a) cin >> x;
    Seg st(a);
    while (m--) {
        int k;
        cin >> k;
        if (k == 1) {
            int a, b;
            cin >> a >> b;
            if (a > b)
                swap(a, b);
            a--, b--;
            cout << st.Query(a, b).ans << "\n";
        } else {
            int p, s;
            cin >> p >> s;
            p--;
            st.Update(p, Kadane(s));
        }
    }
 }
 auto FAST_IO = cin.tie(nullptr)->sync_with_stdio(false);

连续子段

我们运用和上面相似的思想，把「最大子段和」替换为「最大连续出现 1 的长度」，便成了这个玩意。

在这里我们合并的时候不是直接合并，而是判断节点的后缀/前缀连续子段是否等于其本身才能合并，例如：

Info operator+(const Info &l, const Info &r) {
    if (l.len == 0)
        return r;
    if (r.len == 0)
        return l;

    Info res = {};
    res.len = l.len + r.len;
    res.sum = l.sum + r.sum;

    res.pre1 = l.pre1;
    if (l.pre1 == l.len)
        res.pre1 += r.pre1;
    res.suf1 = r.suf1;
    if (r.suf1 == r.len)
        res.suf1 += l.suf1;
    res.ans1 = max({l.ans1, r.ans1, l.suf1 + r.pre1});

    res.pre0 = l.pre0;
    if (l.pre0 == l.len)
        res.pre0 += r.pre0;
    res.suf0 = r.suf0;
    if (r.suf0 == r.len)
        res.suf0 += l.suf0;
    res.ans0 = max({l.ans0, r.ans0, l.suf0 + r.pre0});

    return res;
}

这里就是下面例题的合并操作，具体可以看我写的代码。

例题二

洛谷：P2572 [SCOI2010] 序列操作

维护一堆操作。

参考实现
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) std::println(std::cerr, "{}:\n{}", #x, x)

template <class S, class F> struct LazySegTree {
    int n;
    std::vector<S> tree;
    std::vector<F> tag;

    void pull(int p) { tree[p] = tree[2 * p] + tree[2 * p + 1]; }

    void apply(int p, F f) {
        tree[p] *= f;
        tag[p] += f;
    }

    void push(int p) {
        if (tag[p] == F{})
            return;
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = {};
    }

    void build(auto &&v, int p, int l, int r) {
        if (l == r) {
            tree[p] = S(v[l]);
            return;
        }
        int mid = l + (r - l) / 2;
        build(v, 2 * p, l, mid);
        build(v, 2 * p + 1, mid + 1, r);
        pull(p);
    }

    S query(int ql, int qr, int p, int l, int r) {
        if (ql > r or qr < l)
            return {};
        if (ql <= l and r <= qr)
            return tree[p];
        push(p);
        int mid = l + (r - l) / 2;
        return query(ql, qr, 2 * p, l, mid) +
               query(ql, qr, 2 * p + 1, mid + 1, r);
    }

    void update(int ul, int ur, F f, int p, int l, int r) {
        if (ul > r or ur < l)
            return;
        if (ul <= l and r <= ur) {
            apply(p, f);
            return;
        }
        push(p);
        int mid = l + (r - l) / 2;
        update(ul, ur, f, 2 * p, l, mid);
        update(ul, ur, f, 2 * p + 1, mid + 1, r);
        pull(p);
    }

    LazySegTree() : n(0) {}
    LazySegTree(int _n) : n(_n), tree(4 * n, {}), tag(4 * n, {}) {}
    LazySegTree(auto &&v) : n(v.size()) {
        tree.resize(4 * n);
        tag.resize(4 * n, {});
        build(v, 1, 0, n - 1);
    }

    S Query(int l, int r) { return query(l, r, 1, 0, n - 1); }

    void Update(int l, int r, F f) { update(l, r, f, 1, 0, n - 1); }
};

struct Tag {
    int val = -1;
    bool inv = false;

    Tag() : val(-1), inv(false) {}
    Tag(int val, int inv) : val(val), inv(inv) {}

    friend Tag &operator+=(Tag &, const Tag &);
    bool operator==(const Tag &o) const {
        return val == o.val and inv == o.inv;
    }
};

struct Info {
    int len = 0;
    int sum = 0;
    int pre0 = 0, suf0 = 0, ans0 = 0;
    int pre1 = 0, suf1 = 0, ans1 = 0;

    Info() = default;
    Info(int val) {
        *this = {};
        len = 1;
        if (val == 1) {
            sum = 1;
            pre1 = suf1 = ans1 = 1;
        } else {
            sum = 0;
            pre0 = suf0 = ans0 = 1;
        }
    }

    friend Info operator+(const Info &, const Info &);
    friend Info &operator*=(Info &, const Tag &);
};

Info operator+(const Info &l, const Info &r) {
    if (l.len == 0)
        return r;
    if (r.len == 0)
        return l;

    Info res = {};
    res.len = l.len + r.len;
    res.sum = l.sum + r.sum;

    res.pre1 = l.pre1;
    if (l.pre1 == l.len)
        res.pre1 += r.pre1;
    res.suf1 = r.suf1;
    if (r.suf1 == r.len)
        res.suf1 += l.suf1;
    res.ans1 = max({l.ans1, r.ans1, l.suf1 + r.pre1});

    res.pre0 = l.pre0;
    if (l.pre0 == l.len)
        res.pre0 += r.pre0;
    res.suf0 = r.suf0;
    if (r.suf0 == r.len)
        res.suf0 += l.suf0;
    res.ans0 = max({l.ans0, r.ans0, l.suf0 + r.pre0});

    return res;
}

Tag &operator+=(Tag &l, const Tag &r) {
    if (r.val != -1) {
        l.val = r.val;
        l.inv = r.inv;
    } else if (r.inv) {
        if (l.val != -1) {
            l.val = 1 - l.val;
        } else {
            l.inv = !l.inv;
        }
    }
    return l;
}

Info &operator*=(Info &s, const Tag &f) {
    if (s.len == 0)
        return s;

    if (f.val != -1) {
        if (f.val == 1) {
            s.sum = s.len;
            s.pre1 = s.suf1 = s.ans1 = s.len;
            s.pre0 = s.suf0 = s.ans0 = 0;
        } else {
            s.sum = 0;
            s.pre1 = s.suf1 = s.ans1 = 0;
            s.pre0 = s.suf0 = s.ans0 = s.len;
        }
    }

    if (f.inv) {
        s.sum = s.len - s.sum;
        swap(s.pre0, s.pre1);
        swap(s.suf0, s.suf1);
        swap(s.ans0, s.ans1);
    }
    return s;
}

using SegTree = LazySegTree<Info, Tag>;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> ina(n);
    for (auto &x : ina)
        cin >> x;
    SegTree st(ina);
    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 0) {
            st.Update(l, r, Tag{0, false});
        }
        if (op == 1) {
            st.Update(l, r, Tag{1, false});
        }
        if (op == 2) {
            st.Update(l, r, Tag{-1, true});
        }
        if (op == 3) {
            cout << st.Query(l, r).sum << "\n";
        }
        if (op == 4) {
            cout << st.Query(l, r).ans1 << "\n";
        }
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    while (T--)
        solve();
    return 0;
}

感觉差不多写完了🤔，但其实是我困了，睡觉。
以上。

  1. 这种指的是维护区间最大子段和/最大连续子段。 ↩︎

最近更新
赣ICP备2024042422号
Copyright © 2025 Mohao CC BY-NC-SA 4.0 Licensed