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

线段树原理和代码详解

news 来源：原创 2025/5/9 14:11:23

线段树维护的信息类型

线段树的结构

线段树的初始化

线段树的功能：

单点修改，区间查询

区间修改，区间查询

以下内容均为个人见解，如有不足还请指出，作者会及时修改！

期待大家的点赞、收藏、评论！！！诸君共勉！！！

线段树维护的信息类型

父范围上的某个信息，可以用O(1)的时间，从子范围的信息加工得到。比如：累加和、最大值、最小值。而像某个区间内出现次数最多的数就不行。

线段树的经典功能，如下操作单次调用的时间复杂度是O（logN）

1.范围查询，包括范围内累加和、最大值、最小值等信息。

2.范围修改，包括范围内每个数都增加、重置等操作。

线段树的组织（以最经典的累加和为列）

1.线段树一般以1为最开始的下标

2.线段树在初始化时，就指定范围的数据规模[1,n],一旦确定范围不能修改

3.任何一个大范围的[l,r],可以通过其中点mid，拆分成左范围[l,mid]和右范围[mid+1,r]

线段树的结构

struct Node
{
int l, r;表示范围左右边界
int sum = 0;//表示该范围的累加和

//Int lz=0;懒标记，区间修改用到
};

线段树的初始化

Node tree[N << 2];//线段树的数组表示形式
int arr[N];//原数据数组
void build(int p, int l, int r)
{
   tree[p] = { l,r };//左右边界初始化
   if (l == r)//叶子结点,范围内只有一个数据
   {
       tree[p].sum = arr[l];
       return;
   }
   int mid = l + r >> 1;

//将范围分成左右两个范围
   build(p << 1, l, mid);
   build(p << 1 | 1, mid + 1, r);

   tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
}

这里有个问题，如果线段树的数据范围是1~n,那么线段树的数组需要开多大呢？答案是4n

推理过程：

范围为1~n的数据，形成满二叉树的高度最高是(logn+2)，那么这颗二叉树的结点数就是2^h=2^(logn+2)=4n

线段树的功能：

单点修改，区间查询

1.单点修改：除了要对目标点进行修改，还要对路过的所有点进行更新

如上图所示，对3位置数据+1，还要对3~4范围数据+1,1~4范围数据+1

void add(int p, int x, int k)
{
   if (tree[p].l == tree[p].r)//说明找到该点
   {
       tree[p].sum += k;
       return;
   }
   if (tree[p << 1].r >= x)
       add(p << 1, x, k);
   else
       add(p << 1 | 1, x, k);

   tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;//更新路过的所有点
}

区间查询：如上面初始化数据的图，如果我们查询1~3范围的数据累加和，先从根节点开始查询，发现根节点的范围（1~4）比所要查找的范围大，发现其左右孩子的区间都与所要查找的区间范围有交集，所以开始查询其左右孩子的区间范围，左孩子的范围（1~2）被完全包含在所要查找的范围内，所以直接返回这个区间的值3，右孩子的范围（3~4），发现其左孩子的范围与所要查找的区间有交集，所以查询左孩子，并返回3，最后得到结果3+3=6。

我们总结一下，线段树的查询方法：

如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
如果这个区间的左儿子和目标区间有交集，那么搜索左儿子
如果这个区间的右儿子和目标区间有交集，那么搜索右儿子

int ans = 0;
void query(int p, int l, int r)
{
   if (tree[p].l >= l && tree[p].r <= r)
   {
       ans+= tree[p].sum;
       return;
   }

   if (tree[p << 1].r >= l)//左孩子的右边界如果大于目标区间的左边界，代表有交集
       query(p << 1, l, r);
   if (tree[p << 1 | 1].l <= r)//右孩子的左边界如果小于目标区间的有边界，代表有交集
       query(p << 1 | 1, l, r);
}

区间修改，区间查询

区间修改的时候，我们按照如下原则：

1、如果当前区间被完全覆盖在目标区间里，讲这个区间的sum+k*(tree[i].r-tree[i].l+1)，并对其进行懒标记

2、如果没有完全覆盖，则先下传懒标记

3、如果这个区间的左儿子和目标区间有交集，那么搜索左儿子

4、如果这个区间的右儿子和目标区间有交集，那么搜索右儿子

如下图所示，对1~3范围数据进行+2操作

void down(int p)
{
   if (tree[p].lz)//存在懒标记
   {

//懒标记向下传递给左右孩子
       tree[p << 1].lz += tree[p].lz;
       tree[p << 1|1].lz += tree[p].lz;
       int mid = tree[p].l + tree[p].r >> 1;
       tree[p << 1].sum += tree[p].lz * (mid - tree[p << 1].l + 1);
       tree[p << 1 | 1].sum += tree[p].lz * (tree[p << 1 | 1].r - mid);
       tree[p].lz = 0;
   }
}
//区间修改
void add(int p, int l, int r, int k)
{
   if (tree[p].l >= l && tree[p].r <= r)
   {
       tree[p].sum += k * (tree[p].r - tree[p].l + 1);//区间有几个数据，就加几个k
       tree[p].lz = k;
       return;
   }
   down(p);//懒标记向下传递

   if (tree[p << 1].r >= l)
       add(p << 1, l, r, k);
   if (tree[p << 1 | 1].l <= r)
       add(p << 1 | 1, l, r, k);
   tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;//更新范围累加和
}

区间查询时也要结合懒机制

上面我们已经进行了1~3范围的+2操作，此时如果我们查询范围2~4。

根节点1~4，左右孩子都与目标区间有交集，查询到1~2范围时，发现这个范围有懒标记lz=2,与目标区间有交集2，此时我们需要把这个懒标记向下传递才能得到2的正确值。而3~4范围直接包含在目标范围内，所以直接返回其sum。

int ans = 0;
//范围查询
void query(int p, int l, int r)
{
   if (tree[p].l >= l && tree[p].r <= r)
   {
       ans += tree[p].sum;
       return;
   }
   down(p);//没有完全包含范围，如果存在懒标记需要向下传递
   if (tree[p << 1].r >= l)
       query(p << 1, l, r);
   if (tree[p << 1 | 1].l <= r)
       query(p << 1 | 1, l, r);
}

这里注意如果修改操作是单点修改，那么懒机制也就不需要建立，每次修改直接一走到底就行。

线段树维护的信息类型

线段树的结构

线段树的初始化

线段树的功能：

单点修改，区间查询

区间修改，区间查询

相关文章：