基于线段树的0-1数组区间操作问题求解咨询

针对这个问题，用带懒标记的线段树就能高效解决，核心是用懒标记延迟处理区间赋值操作，避免每次都遍历到叶子节点。

线段树节点设计 #

每个线段树节点需要存储两个关键信息：

• sum：当前节点对应区间内1的总数
• lazy：懒标记，用三种状态表示：
  • -1：无待执行的区间赋值操作
  • 0：需要将当前区间所有元素置为0
  • 1：需要将当前区间所有元素置为1

核心操作实现 #

1. 懒标记下传（push_down） #

当节点存在未处理的懒标记时，需要将标记传递给子节点，更新子节点的状态：

• 左子节点：sum = 懒标记值 * 左子区间长度，lazy = 懒标记值
• 右子节点：同理更新
• 清除当前节点的懒标记（设为-1）

2. 区间置位操作（update_range） #

• 如果当前节点的区间完全被目标区间覆盖：
  • 若要置1，sum = 当前区间长度；若置0，sum = 0
  • 设置当前节点的lazy为对应的值（0或1），直接返回
• 若当前节点有懒标记，先执行push_down下传标记
• 递归处理左、右子节点（仅处理与目标区间重叠的子区间）
• 更新当前节点的sum为左、右子节点的sum之和

3. 区间查询1的数量（query_range） #

• 如果当前节点的区间完全在目标区间内，直接返回sum
• 若当前节点有懒标记，先执行push_down下传标记
• 根据左右子区间与目标区间的重叠情况，递归查询对应子区间
• 返回左右查询结果的总和

代码示例（C++） #

#include <iostream>
#include <vector>
using namespace std;

struct SegmentTree {
    int n;
    vector<int> sum;
    vector<int> lazy;

    SegmentTree(const vector<int>& arr) {
        n = arr.size();
        sum.resize(4 * n);
        lazy.resize(4 * n, -1);
        build(0, 0, n - 1, arr);
    }

    void build(int node, int l, int r, const vector<int>& arr) {
        if (l == r) {
            sum[node] = arr[l];
            return;
        }
        int mid = (l + r) / 2;
        build(2*node+1, l, mid, arr);
        build(2*node+2, mid+1, r, arr);
        sum[node] = sum[2*node+1] + sum[2*node+2];
    }

    void push_down(int node, int l, int r) {
        if (lazy[node] == -1) return;
        int mid = (l + r) / 2;
        int left = 2*node+1, right_node = 2*node+2;
        // 更新左子节点
        sum[left] = lazy[node] * (mid - l + 1);
        lazy[left] = lazy[node];
        // 更新右子节点
        sum[right_node] = lazy[node] * (r - mid);
        lazy[right_node] = lazy[node];
        // 清除当前节点懒标记
        lazy[node] = -1;
    }

    void update_range(int ul, int ur, int val) {
        update(0, 0, n-1, ul, ur, val);
    }

    void update(int node, int l, int r, int ul, int ur, int val) {
        if (ur < l || ul > r) return;
        if (ul <= l && r <= ur) {
            sum[node] = val * (r - l + 1);
            lazy[node] = val;
            return;
        }
        push_down(node, l, r);
        int mid = (l + r) / 2;
        update(2*node+1, l, mid, ul, ur, val);
        update(2*node+2, mid+1, r, ul, ur, val);
        sum[node] = sum[2*node+1] + sum[2*node+2];
    }

    int query_range(int ql, int qr) {
        return query(0, 0, n-1, ql, qr);
    }

    int query(int node, int l, int r, int ql, int qr) {
        if (qr < l || ql > r) return 0;
        if (ql <= l && r <= qr) return sum[node];
        push_down(node, l, r);
        int mid = (l + r) / 2;
        return query(2*node+1, l, mid, ql, qr) + query(2*node+2, mid+1, r, ql, qr);
    }
};

int main() {
    // 示例：初始数组0100101（索引从0开始对应[0,1,0,0,1,0,1]）
    vector<int> arr = {0,1,0,0,1,0,1};
    SegmentTree st(arr);
    // 将1到3位置（题目1-based转0-based为0到2）置为1
    st.update_range(0, 2, 1);
    // 将2到5位置（题目1-based转0-based为1到4）置为0
    st.update_range(1, 4, 0);
    // 查询2到7位置（题目1-based转0-based为1到6）的1的数量
    cout << st.query_range(1, 6) << endl; // 输出1，符合示例结果
    return 0;
}

复杂度分析 #

• 建树时间：O(n)
• 单次区间置位/查询操作：O(logn)
• q次操作总时间复杂度：O(qlogn)，远优于暴力解法的O(nq)，适合处理大规模数据和高频操作场景

内容的提问来源于stack exchange，提问作者dispenomi