每日算法 — 使用java实现线段树Beats：区间取模与区间最值维护

可莉爸爸 AI算法

引言

传统线段树可以高效处理区间求和、区间最值、区间加减等操作，时间复杂度均为 O(log n)。但当问题升级到区间取模、区间取 min/max（即每个元素与某个值取较小/较大值）时，普通的 lazy propagation 会失效——因为这些操作不满足”区间整体可加性”。

线段树 Beats（由 ILO 于 2017 年在 Codeforces 博客中提出并命名）正是为解决这类问题而生的高级数据结构。它在传统线段树的基础上增加了次大值维护和计数统计，使得区间 chmin/chmax（change min / change max）操作也能在均摊 O(log n) 时间内完成。

本文将用 Java 完整实现线段树 Beats，支持区间求和、区间取 min、区间取 max 操作。

算法原理

为什么传统线段树处理不了区间 chmin？

考虑对一个区间 [l, r] 执行 a[i] = min(a[i], x)。如果区间内所有元素都大于 x，那没问题，直接更新即可。但如果只有部分元素大于 x，传统线段树的 lazy tag 无法表达这种”只影响部分元素”的操作。

核心洞察

线段树 Beats 的关键洞察是：对于 chmin 操作，只有大于 x 的元素会改变。如果区间内最大值 mx 都 <= x，则无需任何操作。如果有元素大于 x，那么：

  1. 所有大于 x 的元素都会被压到 x
  2. 如果次大值 se < x < mx，则只有最大值需要改变——这可以用类似 lazy tag 的方式批量处理
  3. 如果 x <= se，则需要继续下推到子节点

维护的信息

每个节点需要维护：
– sum：区间和
– mx：区间最大值
– cmx：最大值出现的次数
– se：区间次大值（严格小于 mx 的最大值，若不存在则为 -∞）
– mn：区间最小值（对称维护，用于 chmax）
– cmn：最小值出现次数
– se_min：区间次小值

Java 实现

1. 核心数据结构

/**
 * 线段树Beats节点
 * 同时维护最大值和最小值信息，支持区间chmin/chmax
 */
class BeatsNode {
    long sum;       // 区间和

    // 最大值相关信息
    long mx;        // 区间最大值
    int cmx;        // 最大值出现次数
    long se;        // 次大值（严格小于mx）

    // 最小值相关信息
    long mn;        // 区间最小值
    int cmn;        // 最小值出现次数
    long seMin;     // 次小值（严格大于mn）

    public BeatsNode() {
        this.sum = 0;
        this.mx = Long.MIN_VALUE;
        this.cmx = 0;
        this.se = Long.MIN_VALUE;
        this.mn = Long.MAX_VALUE;
        this.cmn = 0;
        this.seMin = Long.MAX_VALUE;
    }
}

/**
 * 线段树Beats完整实现
 * 支持：区间求和、区间chmin、区间chmax
 */
public class SegmentTreeBeats {

    private final int n;
    private final long[] arr;
    private final BeatsNode[] tree;

    public SegmentTreeBeats(long[] arr) {
        this.n = arr.length;
        this.arr = arr.clone();
        this.tree = new BeatsNode[n * 4];
        for (int i = 0; i < tree.length; i++) {
            tree[i] = new BeatsNode();
        }
        build(1, 0, n - 1);
    }

    /**
     * 构建线段树
     */
    private void build(int node, int l, int r) {
        if (l == r) {
            tree[node].sum = arr[l];
            tree[node].mx = arr[l];
            tree[node].cmx = 1;
            tree[node].se = Long.MIN_VALUE;
            tree[node].mn = arr[l];
            tree[node].cmn = 1;
            tree[node].seMin = Long.MAX_VALUE;
            return;
        }

        int mid = (l + r) >>> 1;
        build(node << 1, l, mid);
        build(node << 1 | 1, mid + 1, r);
        pull(node);
    }

    /**
     * 从子节点合并信息到父节点
     */
    private void pull(int node) {
        BeatsNode left = tree[node << 1];
        BeatsNode right = tree[node << 1 | 1];
        BeatsNode cur = tree[node];

        // 合并和
        cur.sum = left.sum + right.sum;

        // 合并最大值信息
        if (left.mx > right.mx) {
            cur.mx = left.mx;
            cur.cmx = left.cmx;
            cur.se = Math.max(left.se, right.mx);
        } else if (left.mx < right.mx) {
            cur.mx = right.mx;
            cur.cmx = right.cmx;
            cur.se = Math.max(left.mx, right.se);
        } else {
            cur.mx = left.mx;
            cur.cmx = left.cmx + right.cmx;
            cur.se = Math.max(left.se, right.se);
        }

        // 合并最小值信息
        if (left.mn < right.mn) {
            cur.mn = left.mn;
            cur.cmn = left.cmn;
            cur.seMin = Math.min(left.seMin, right.mn);
        } else if (left.mn > right.mn) {
            cur.mn = right.mn;
            cur.cmn = right.cmn;
            cur.seMin = Math.min(left.mn, right.seMin);
        } else {
            cur.mn = left.mn;
            cur.cmn = left.cmn + right.cmn;
            cur.seMin = Math.min(left.seMin, right.seMin);
        }
    }

    /**
     * 对节点应用chmin操作：将所有大于x的元素变为x
     * 前提条件：x >= node.se（确保只有最大值需要改变）
     */
    private void pushChmin(int node, long x) {
        BeatsNode cur = tree[node];
        if (cur.mx <= x) return; // 无需操作

        // 更新和：将cmx个最大值从mx改为x
        cur.sum -= (cur.mx - x) * cur.cmx;
        cur.mx = x;

        // 注意：mn也可能等于旧mx，需要同步更新
        if (cur.mn > x) {
            cur.mn = x;
        }
        // 如果mn等于旧mx，且只有一个最小值，需要更新
        // 但这种情况在se维护正确时不会发生
    }

    /**
     * 对节点应用chmax操作：将所有小于x的元素变为x
     */
    private void pushChmax(int node, long x) {
        BeatsNode cur = tree[node];
        if (cur.mn >= x) return;

        cur.sum += (x - cur.mn) * cur.cmn;
        cur.mn = x;

        if (cur.mx < x) {
            cur.mx = x;
        }
    }

    /**
     * 下推懒标记到子节点
     */
    private void push(int node) {
        BeatsNode cur = tree[node];

        // 下推chmin
        if (tree[node << 1].mx > cur.mx) {
            pushChmin(node << 1, cur.mx);
        }
        if (tree[node << 1 | 1].mx > cur.mx) {
            pushChmin(node << 1 | 1, cur.mx);
        }

        // 下推chmax
        if (tree[node << 1].mn < cur.mn) {
            pushChmax(node << 1, cur.mn);
        }
        if (tree[node << 1 | 1].mn < cur.mn) {
            pushChmax(node << 1 | 1, cur.mn);
        }
    }
}

2. 区间操作实现

    /**
     * 区间chmin：将[L,R]内所有大于x的元素变为x
     */
    public void rangeChmin(int L, int R, long x) {
        rangeChmin(1, 0, n - 1, L, R, x);
    }

    private void rangeChmin(int node, int l, int r, int L, int R, long x) {
        if (r < L || l > R || tree[node].mx <= x) {
            return; // 无交集或无需操作
        }
        if (L <= l && r <= R && tree[node].se < x) {
            // 完全覆盖且次大值<x：可以直接打标记
            pushChmin(node, x);
            return;
        }

        push(node); // 下推后再递归
        int mid = (l + r) >>> 1;
        rangeChmin(node << 1, l, mid, L, R, x);
        rangeChmin(node << 1 | 1, mid + 1, r, L, R, x);
        pull(node);
    }

    /**
     * 区间chmax：将[L,R]内所有小于x的元素变为x
     */
    public void rangeChmax(int L, int R, long x) {
        rangeChmax(1, 0, n - 1, L, R, x);
    }

    private void rangeChmax(int node, int l, int r, int L, int R, long x) {
        if (r < L || l > R || tree[node].mn >= x) {
            return;
        }
        if (L <= l && r <= R && tree[node].seMin > x) {
            pushChmax(node, x);
            return;
        }

        push(node);
        int mid = (l + r) >>> 1;
        rangeChmax(node << 1, l, mid, L, R, x);
        rangeChmax(node << 1 | 1, mid + 1, r, L, R, x);
        pull(node);
    }

    /**
     * 区间求和查询
     */
    public long rangeSum(int L, int R) {
        return rangeSum(1, 0, n - 1, L, R);
    }

    private long rangeSum(int node, int l, int r, int L, int R) {
        if (r < L || l > R) return 0;
        if (L <= l && r <= R) return tree[node].sum;

        push(node);
        int mid = (l + r) >>> 1;
        return rangeSum(node << 1, l, mid, L, R)
             + rangeSum(node << 1 | 1, mid + 1, r, L, R);
    }

    /**
     * 区间最大值查询
     */
    public long rangeMax(int L, int R) {
        return rangeMax(1, 0, n - 1, L, R);
    }

    private long rangeMax(int node, int l, int r, int L, int R) {
        if (r < L || l > R) return Long.MIN_VALUE;
        if (L <= l && r <= R) return tree[node].mx;

        push(node);
        int mid = (l + r) >>> 1;
        return Math.max(rangeMax(node << 1, l, mid, L, R),
                       rangeMax(node << 1 | 1, mid + 1, r, L, R));
    }

    /**
     * 区间最小值查询
     */
    public long rangeMin(int L, int R) {
        return rangeMin(1, 0, n - 1, L, R);
    }

    private long rangeMin(int node, int l, int r, int L, int R) {
        if (r < L || l > R) return Long.MAX_VALUE;
        if (L <= l && r <= R) return tree[node].mn;

        push(node);
        int mid = (l + r) >>> 1;
        return Math.min(rangeMin(node << 1, l, mid, L, R),
                       rangeMin(node << 1 | 1, mid + 1, r, L, R));
    }

    /**
     * 单点修改（用于初始化和特殊场景）
     */
    public void pointUpdate(int idx, long val) {
        pointUpdate(1, 0, n - 1, idx, val);
    }

    private void pointUpdate(int node, int l, int r, int idx, long val) {
        if (l == r) {
            tree[node].sum = val;
            tree[node].mx = val;
            tree[node].mn = val;
            return;
        }
        push(node);
        int mid = (l + r) >>> 1;
        if (idx <= mid) {
            pointUpdate(node << 1, l, mid, idx, val);
        } else {
            pointUpdate(node << 1 | 1, mid + 1, r, idx, val);
        }
        pull(node);
    }

3. 完整可运行示例

/**
 * 线段树Beats完整测试与演示
 */
public class SegmentTreeBeatsDemo {

    public static void main(String[] args) {
        // 初始化数组
        long[] arr = {5, 3, 8, 12, 7, 2, 10, 15, 4, 9};

        System.out.println("初始数组: " + java.util.Arrays.toString(arr));

        SegmentTreeBeats st = new SegmentTreeBeats(arr);

        // 查询区间和 [0, 4]
        System.out.println("区间[0,4]的和: " + st.rangeSum(0, 4)); // 5+3+8+12+7 = 35

        // 查询区间最大值 [2, 6]
        System.out.println("区间[2,6]的最大值: " + st.rangeMax(2, 6)); // max(8,12,7,2,10) = 12

        // 执行区间chmin [1, 7] x=6：将所有大于6的元素变为6
        // 原数组: [5, 3, 8, 12, 7, 2, 10, 15, 4, 9]
        // chmin后: [5, 3, 6, 6, 6, 2, 6, 6, 4, 9]
        st.rangeChmin(1, 7, 6);
        System.out.println("\n执行 rangeChmin[1,7] x=6 后:");
        System.out.println("区间[0,4]的和: " + st.rangeSum(0, 4)); // 5+3+6+6+6 = 26
        System.out.println("区间[2,6]的最大值: " + st.rangeMax(2, 6)); // max(6,6,6,2,6) = 6

        // 执行区间chmax [3, 8] x=5：将所有小于5的元素变为5
        // 当前: [5, 3, 6, 6, 6, 2, 6, 6, 4, 9]
        // chmax后: [5, 3, 6, 6, 6, 5, 6, 6, 5, 9]
        st.rangeChmax(3, 8, 5);
        System.out.println("\n执行 rangeChmax[3,8] x=5 后:");
        System.out.println("区间[3,8]的和: " + st.rangeSum(3, 8)); // 6+6+5+6+6+5 = 34
        System.out.println("区间[3,8]的最小值: " + st.rangeMin(3, 8)); // 5

        // 连续多次chmin（测试均摊复杂度）
        System.out.println("\n连续chmin测试:");
        for (int i = 10; i >= 1; i--) {
            st.rangeChmin(0, 9, i);
            System.out.println("chmin x=" + i + ", 总和=" + st.rangeSum(0, 9));
        }
        // 最终所有元素应该都被压到1
        System.out.println("最终区间[0,9]的最大值: " + st.rangeMax(0, 9)); // 1
    }
}

4. 区间取模扩展

    /**
     * 区间取模操作：a[i] %= x
     * 利用性质：若 a[i] < x，则 a[i] % x = a[i]（不变）
     * 若 a[i] >= x，则 a[i] % x < x，相当于一次chmin操作
     */
    public void rangeModulo(int L, int R, long x) {
        rangeModulo(1, 0, n - 1, L, R, x);
    }

    private void rangeModulo(int node, int l, int r, int L, int R, long x) {
        if (r < L || l > R || tree[node].mx < x) {
            return; // 所有元素都小于x，无需操作
        }
        if (l == r) {
            // 叶子节点直接取模
            tree[node].sum %= x;
            tree[node].mx = tree[node].sum;
            tree[node].mn = tree[node].sum;
            return;
        }

        push(node);
        int mid = (l + r) >>> 1;
        rangeModulo(node << 1, l, mid, L, R, x);
        rangeModulo(node << 1 | 1, mid + 1, r, L, R, x);
        pull(node);
    }

复杂度分析

时间复杂度

线段树 Beats 的核心复杂度在于chmin/chmax 操作：

  • 单次 chmin/chmax：均摊 O(log n)
  • 均摊分析依据：每个元素被修改的次数有限。对于 chmin 操作，一个元素只有在其为区间最大值时才会被修改，而每次修改后它至少变成次大值或更小。一个元素最多被修改 O(log V) 次（V 为值域），因此均摊复杂度为 O(log n)
  • 区间求和/最值查询：O(log n)
  • 区间取模：均摊 O(log n × log V)

空间复杂度

  • 树节点数组：O(4n)，每个节点存储 7 个字段（sum, mx, cmx, se, mn, cmn, seMin）
  • 总空间：约 4n × (8×4 + 4×2) = 4n × 40 字节 ≈ 160n 字节

应用场景

1. 资源限制调度

假设有 n 个任务，每个任务有一个资源需求量。需要支持：
– 查询某段任务的资源总和
– 将某段任务的资源需求上限设为 x（超过的削减）
– 将某段任务的资源需求下限设为 x（不足的补齐）

这正是线段树 Beats 的标准应用场景。

2. 游戏数值系统

在 RPG 游戏中，角色的多个属性需要同时维护：
– 对某类敌人伤害不超过某个阈值（chmin）
– 对某类敌人伤害不低于某个阈值（chmax）
– 查询当前属性总和

3. 区间取模问题

经典问题：维护一个数组，支持区间求和、区间取模。由于 a % x 当 a < x 时不变，当 a >= x 时结果 < x，可以转化为多次 chmin 操作。

进阶扩展

支持区间加法和区间覆盖

在完整版的线段树 Beats 中，还可以同时支持：
– 区间加法：传统 lazy tag 处理
– 区间覆盖：优先级最高，直接覆盖所有信息

实现时需要注意操作优先级：覆盖 > chmin/chmax > 加法

空间优化

对于 n <= 10^5 的场景，4 倍空间足够。对于 n <= 10^6 的大规模数据：
– 使用迭代式线段树（非递归）减少常数
– 动态开点（只有需要的节点才创建）

总结

线段树 Beats 通过次大值维护这一巧妙设计，突破了传统线段树无法高效处理区间 chmin/chmax 的瓶颈。本文的 Java 实现展示了：

  1. 双端信息维护：同时维护最大值和最小值，支持双向区间限制
  2. 次值判断：利用 se < x < mx 的条件实现 O(1) 的批量更新
  3. 均摊复杂度：每个元素修改次数有限，保证整体效率
  4. 区间取模扩展：将取模转化为 chmin 的巧妙转化

在算法竞赛中，线段树 Beats 是处理区间最值修改问题的终极武器；在实际工程中，它也是资源调度、数值限制等场景的高效解决方案。

Tagged with: