Quartz 5

线段树

6 min read

定义

线段树（Segment Tree）是一种二叉树结构，能在 O(logN) 内快速查询和修改区间信息，常用于处理区间和、区间最值、区间覆盖等问题。

建树

int a[N], tree[N << 2], lazy[N << 2];  
void build(const int node, const int start, const int end)  
{  
    if (start == end) // 叶子节点  
        tree[node] = a[start];  
    else  
    {  
        // mid = (start + end) / 2 , left = node * 2, right = node * 2 + 1  
        const int mid = (start + end) >> 1, left = node << 1, right = node << 1 | 1;  
        build(left, start, mid); // 左子树  
        build(right, mid + 1, end); // 右子树  
        tree[node] = tree[left] + tree[right]; // 父节点  
    }  
}

例：

build(1, 0, N - 1);

查询

无延迟更新

int a[N], tree[N << 2];
int query(const int node, const int start, const int end, const int left, const int right)  
{  
    if (left > end || right < start) // 查询区间与当前区间不相交  
        return 0;  
    if (left <= start && end <= right) // 查询区间完全包含当前区间  
        return tree[node];  
    const int mid = (start + end) >> 1; // 部分包含，结果=左子树包含查询区间的部分+右子树包含查询区间的部分  
    return query(node << 1, start, mid, left, right) + query(node << 1 | 1, mid + 1, end, left, right);  
}

例：

int sum = query(1, 0, N + 1, 3 , 5); //查询[3,5]的区间和

延迟更新

int a[N], tree[N << 2], lazy[N << 2];  
int query(const int node, const int start, const int end, const int left,const int right)  
{  
    if (lazy[node])// 当前节点有延迟更新，处理当前节点的延迟更新  
    {  
        tree[node] += (end - start + 1) * lazy[node]; // 更新当前节点  
        if (start != end) // 如果不是叶子节点，传播延迟更新  
        {  
            lazy[node << 1] += lazy[node]; // 左子树延迟更新  
            lazy[node << 1 | 1] += lazy[node]; // 右子树延迟更新  
        }  
        lazy[node] = 0; // 清除当前节点的延迟更新  
    }  
    if (left > end || right < start) // 查询区间与当前区间不相交  
        return 0;  
    if (left <= start && end <= right) // 查询区间完全包含当前区间  
        return tree[node];  
    const int mid = (start + end) >> 1; // 部分包含，结果 = 左子树包含查询区间的部分 + 右子树包含查询区间的部分  
    return query(node << 1, start, mid, left, right) + query(node << 1 | 1, mid + 1, end, left, right);  
}

更新

无延迟更新

更新单个节点

int a[N], tree[N << 2];
void update(const int node, const int start, const int end, const int index, const int value)  
{  
    if (start == end) // 如果是叶子节点说明这个节点就是要更新的节点  
        tree[node] = value;  
    else  
    {  
        const int mid = (start + end) >> 1; // mid = (start + end) / 2  
        if (index <= mid) // 要更新的节点在左子树，更新左子树  
            update(node << 1, start, mid, index, value);  
        else // 要更新的节点在右子树，更新右子树  
            update(node << 1 | 1, mid + 1, end, index, value);  
        tree[node] = tree[node << 1] + tree[node << 1 | 1]; // 更新父节点  
    }  
}

延迟更新

更新区间

int a[N], tree[N << 2], lazy[N << 2];
void update(const int node, const int start, const int end, const int left, const int right, const int value)  
{  
    if (lazy[node]) // 当前节点有延迟更新，处理当前节点的延迟更新
    {  
        tree[node] += (end - start + 1) * lazy[node]; // 更新当前节点  
        if (start != end) // 如果不是叶子节点，传播延迟更新
        {  
            lazy[node << 1] += lazy[node]; // 左子树延迟更新  
            lazy[node << 1 | 1] += lazy[node]; // 右子树延迟更新  
        }  
        lazy[node] = 0; // 清除当前节点的延迟更新  
    }  
    if (left > end || right < start) // 更新区间与当前区间不相交  
        return;  
    if (left <= start && end <= right) // 更新区间完全包含当前区间  
    {  
        tree[node] += (end - start + 1) * value; // 更新当前区间  
        if (start != end)  
        {  
            lazy[node << 1] += value; // 左子树延迟更新  
            lazy[node << 1 | 1] += value; // 右子树延迟更新  
        }  
        return;  
    }  
    const int mid = (start + end) >> 1; // 部分包含，更新左子树和右子树  
    update(node << 1, start, mid, left, right, value); // 更新左子树  
    update(node << 1 | 1, mid + 1, end, left, right, value); // 更新右子树  
    tree[node] = tree[node << 1] + tree[node << 1 | 1]; // 更新当前节点  
}

模板