线段树

基本概念

线段树是一棵 完全二叉树，用于在 静态数组 上快速完成区间查询（如区间和、区间最大值等）和单点更新。
每个节点维护一个区间的信息，根节点代表整个区间，左右子节点分别代表区间的前后半部分。

构建流程

  1. 准备大小为 4×LEN4\times LEN 的数组 tree 来存储节点值。
  2. 从根节点开始，递归构建：
    • 如果区间左端点 = 右端点，直接把原始数组的值写入该节点。
    • 否则，计算中点 midmid，分别构建左右子区间，并将左右子区间结果合并到父节点。
1
2
3
4
5
6
7
8
9
10
11
12
void build(int idx,int l,int r)
{
    if(l==r)//叶子节点
    {
        tree[idx]=arr[l];
        return;
    }
    int mid=(l+r)>>1;
    build(idx<<1,l,mid);//左子树
    build(idx<<1|1,mid+1,r);//右子树
    tree[idx]=tree[idx<<1]+tree[idx<<1|1];//求区间和
}

区间查询

  1. 从根节点开始，看当前节点区间 [l,r][l, r] 是否与查询区间 [L,R][L, R] 完全重合。
  2. 如果完全重合，直接返回该节点值。
  3. 否则，根据中点 midmid 决定向左或右子树深入，或者分成两部分递归查询，再把结果相加。
1
2
3
4
5
6
7
8
int query(int idx,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)  return tree[idx];//区间重合
    int mid=(l+r)>>1,sum=0;
    if(L<=mid)  sum+=query(idx<<1,l,mid,L,R);//左子树
    if(mid<R)  sum+=query(idx<<1|1,mid+1,r,L,R);//右子树
    return sum;
}

单点更新

  1. 定位到要更新的叶子节点，修改其值。
  2. 递归返回时，依次在父节点更新合并后的值，保持整棵树信息正确。
1
2
3
4
5
6
7
8
9
10
11
12
void update(int idx,int l,int r,int pos,int val)
{
    if(l==r)//叶子节点
    {
        tree[idx]=val;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(idx<<1,l,mid,pos,val);//左子树
    else update(idx<<1|1,mid+1,r,pos,val);//右子树
    tree[idx]=tree[idx<<1]+tree[idx<<1|1];
}

代码示例

例题：Luogu P3372 - 【模板】线段树 1

题意

维护长度为 n 的序列，支持两种操作：

  1. 区间 [l, r] 每个数加上同一个值
  2. 查询区间 [l, r] 的所有数之和

输入格式

  • 第一行 n，m
  • 第二行 nn 个初始值
  • 接下来 mm 行，每行三种格式：
    • 1 x y k 表示给区间 [x, y] 的每个数加上 k
    • 2 x y 表示询问区间 [x, y] 的和

数据范围

  • 1≤n,m≤1051\le n,m\le 10^5

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int LEN=1e5+5;
struct Node
{
    int sum,tag;
    //sum:区间和，tag:懒惰标记
}tr[LEN*4];

int n,m;
int a[LEN];

void pushup(int u)//更新父节点
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
    return;
}

void apply(int u,int l,int r,int v)//更新子节点
{
    tr[u].sum+=v*(r-l+1);
    tr[u].tag+=v;
    return;
}

void pushdown(int u,int l,int r)//下传懒惰标记
{
    if(tr[u].tag)
    {
        int mid=(l+r)>>1;
        apply(u<<1,l,mid,tr[u].tag);
        apply(u<<1|1,mid+1,r,tr[u].tag);
        tr[u].tag=0;
    }
    return;
}

void build(int u,int l,int r)//构建线段树
{
    tr[u].tag=0;
    if(l==r)
    {
        tr[u].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
    return;
}

void update(int u,int l,int r,int L,int R,int v)//区间更新
{
    if(L<=l&&r<=R)
    {
        apply(u,l,r,v);
        return;
    }
    pushdown(u,l,r);
    int mid=(l+r)>>1;
    if(L<=mid)  update(u<<1,l,mid,L,R,v);
    if(mid<R)  update(u<<1|1,mid+1,r,L,R,v);
    pushup(u);
    return;
}

int query(int u,int l,int r,int L,int R)//区间查询
{
    if(L<=l&&r<=R)  return tr[u].sum;
    pushdown(u,l,r);
    int mid=(l+r)>>1;
    int ans=0;
    if(L<=mid)  ans+=query(u<<1,l,mid,L,R);
    if(mid<R)  ans+=query(u<<1|1,mid+1,r,L,R);
    return ans;
}

signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)  cin>>a[i];
    build(1,1,n);

    while(m--)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1)
        {
            int k;
            cin>>k;
            update(1,1,n,x,y,k);
        }
        else  cout<<query(1,1,n,x,y)<<endl;
    }
    return 0;
}

树状数组（Fenwick Tree）

基本概念

树状数组又称 二叉索引树，用于在 动态数组 上快速完成前缀和查询和单点更新。
利用 低位优先 的思想，把数组分成若干层次，实现 O(log n)O(log\ n) 的更新与查询。

初始化

  1. 定义大小为 n+1n+1 的数组 bit，下标从 1 开始。
  2. 遍历原始数组，每次调用一次单点更新，把值累加到 bit 中。
1
2
vector<int> bit(n+1,0);
for(int i=1;i<=n;i++)  add(i,arr[i]);//单点更新

单点更新

  1. 从更新位置 i 开始，依次向后跳到 i+=lowbit(i)，把增量 delta 累加到所有相关节点上。
  2. lowbit(i) = i & -i，表示 i 的最低位权重。
1
2
3
4
5
6
7
8
void add(int i,int delta)
{
    while(i<=n)
    {
        bit[i]+=delta;
        i+=i&-i;
    }
}

前缀和查询

  1. 从查询位置 i 开始，依次向前跳到 i-=lowbit(i)，把所有经过节点的 bit[i] 累加到结果中。
  2. 最终得到前缀和 sum(arr[1..i])。
1
2
3
4
5
6
7
8
9
10
int sum(int i)
{
    int res=0;
    while(i>0)
    {
        res+=bit[i];
        i-=i&-i;
    }
    return res;
}

代码示例

例题：Luogu P3374 - 【模板】树状数组 1

题意

给定长度为 n 的整数序列，初始值 a1,a2,…,ana_1, a_2, \ldots, a_n。需要执行 m 次操作，每次操作有两种类型：

  • 1 x k：将第 x 个数加上 k
  • 2 x y：询问区间 [x,y][x, y] 内所有数之和

输入格式

第一行包含两个整数 n 和 m，分别表示序列长度和操作次数。
第二行包含 n 个整数，为序列的初始值。
接下来 m 行，每行一个操作指令。

数据范围

  • 1≤n,m≤5×1051\le n,m\le 5\times 10^5；
  • 所有加数和初始值的绝对值均不超过 2312^{31}。

解题思路

我们使用 树状数组（Fenwick Tree） 来维护前缀和，支持单点更新和区间查询均为 O(log n)O(log\ n)：

  • 初始化时，将每个 a[i] 插入到树状数组。
  • 对于 “1 x k” 操作，在下标 x 处加上 k，即调用 update(x,k)。
  • 对于 “2 x y” 操作，利用前缀和差值：query(y)-query(x-1)。

核心操作：

  • update(i,v)：从 i 开始，不断 i+=lowbit(i)，将 tree[i] 累加 v。
  • query(i)：从 i 开始，不断 i-=lowbit(i)，累加 tree[i]，直到 i=0。

时间复杂度：O((n+m) log n)O((n+m)\ log\ n)；空间复杂度：O(n)O(n)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int LEN=5e5+5;
int n,m;
int tree[LEN];

//返回最低位 1 的值
inline int lowbit(int x){return x&-x;}

//单点更新：a[i]+=v
void update(int i,int v)
{
    for(;i<=n;i+=lowbit(i))  tree[i]+=v;
    return;
}

//查询前缀和 a[1..i]
int query(int i)
{
    int s=0;
    for(;i>0;i-=lowbit(i))  s+=tree[i];
    return s;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        update(i,x);
    }

    while(m--)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1)  update(x,y);
        else  cout<<query(y)-query(x-1)<<endl;
    }
    return 0;
}

对比总结

数据结构 区间查询 前缀/区间查询 单点更新 空间复杂度
线段树 支持任意区间查询 逻辑同区间查询，O(log n)O(log\ n) O(log n)O(log\ n) O(4n)O(4n)
树状数组 不直接支持任意区间查询 前缀和 O(log n)O(log\ n)，区间和可转化 O(log n)O(log\ n) O(n)O(n)
  • 若需支持区间加值、单点查询，可在树状数组中维护差分数组。
  • 若需支持区间加值、区间查询，则需要 双树状数组 或 差分 + 前缀和 技巧。
  • 对比线段树，树状数组代码更简洁，但不易扩展到区间修改和区间查询的混合场景。
数据提高班
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~