当前位置：首页 > article >正文

线段树与树状数组（C++）

article 2025/2/24 16:41:30

线段树：基于分治思想的二叉树，用于维护区间信息（区间和，区间最值等），区间修改和区间查询的时间复杂度为logn

叶子节点存储元素本身，非叶子节点存取区间信息

1.节点：是一个结构体，包含l,r,sum

l,r为区间左右端点，sum为区间和

struct node{
    int l , r;
    int sum;
}st[N*4];

2.递归建树：

父节点编号为p，左孩子2*p,右孩子2*p+1

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
        //也可以用pushup(u); 因为有节点新增，所以要向上更新
    }
}

3.点修改：

4.区间查询：

拆分和拼凑的思想。

从根节点进入，如果该节点的区间被所查询的区间覆盖了，就直接返回sum ，否则根据左右子节点的重叠情况去往下去递归

5.区间修改：

难点在于理解懒惰修改，懒惰标记

完整代码：

树状数组：线段树阉割掉了一些点，空间比线段树小，时间一样，维护具有结合律和可拆分信息，如加法（和）、乘法（积）、异或等。树状数组能解决的问题是线段树能解决的问题的子集。

性能：代码短，时间常数小

要记住他的三个基本操作 lowbit，add（向后），query（向前）

int lowbit(int x) {
    return x & -x;
}

void add(int x,int v) {
    while (x <= n) tr[x]+=v,x += lowbit(x);
}

int query(int x)
{
    int res = 0;
    while (x) res += tr[x],x -= lowbit(x);
    return res;
}