[高级数据结构C++] 线段树（区间和的查询与修改）
`线段树` 和 `树状数组` 都是很适合解决**区间问题**的数据结构。
》》》算法竞赛
/**
* @file
* @author jUicE_g2R(qq:3406291309)————彬(bin-必应)
* 一个某双流一大学通信与信息专业大二在读
*
* @brief 一直在算法竞赛学习的路上
*
* @copyright 2023.9
* @COPYRIGHT 原创技术笔记：转载需获得博主本人同意，且需标明转载源
*
* @language C++
* @Version 1.0还在学习中
*/
- UpData Log👆 2023.9.10 更新进行中
- Statement0🥇 一起进步
- Statement1💯 有些描述可能不够标准，但能达其意
技术提升站点
17 线段树
线段树 和 树状数组 都是很适合解决区间问题的数据结构。
- 有两个很典型的区间问题：
1）区间最值问题
2）区间和问题
线段树与树状数组各自的优点
| 线段树 | 树状数组 | |
|---|---|---|
| 逻辑结构 | 基于二叉树，数据结构清晰直观 |
没有线段树应用灵活 |
| 代码长度 | 需要维护二叉树，代码更长；但可以用数组写但费空间 | 较简单 |
17-1 基本知识
线段树的实现 =分治思想 +二叉树结构 +Lazy-Tag技术
这个处理方法和 递归排序 有异曲同工之妙！
上图中每个节点是一个区间段，当区间的左右端点相同时就是 叶子结点。
17-1-1 构造线段树的存储结构
法一：构造结构体
//设定根节点为tree[1]
const int N=1e5+10;
const long long int MAX=4N;
struct node{
int Lson,Rson; //左孩子，右孩子
int data; //自己的数据（区间最值/区间和）
}tree[MAX];
法二：直接用数组，更省空间
vector<int> tree(MAX,0);
int Get_LeftSon(int id) {return id<<1;} //return id*2;
int Get_RightSon(int id){return id<<1|1;} //return (id*2+1);
法三：指针（用结构体）
using ElemType=int;
struct node{
ElemType data;
node* Lson; node* Rson;
node():data(0),Lson(nullptr),Rson(nullptr){}//初始化
};
二叉树开辟的数组空间是元素数量 N 的 4倍的原因
若最下面的一层只储存一个节点且上面所有层均被填满，则最下面的一层使用了约为 2N 格空间，反推回去，倒数第二层使用了 N 格空间，其余层使用了 N 格空间，则加在一起就是 4N。
17-1-2 构造树结构
支架逻辑
- 求区间和
//使用法二的存储结构，tree数组存储该节点树段的区间和
void Get_Parent(int id){
tree[id]=tree[Get_LeftSon(id)] + tree[Get_RightSon(id)];//自下而上传递
}
- 求区间最值
void Get_Maximum(int id){
tree[id]=min(tree[Get_LeftSon(id)] , tree[Get_RightSon(id)];)//将左右子结点比较后的结果返给父结点
}
树形
//我们对 Get_LeftSon 重命名为 Ls
void Build_Tree(int P,int L,int R){ //父节点以及他的左右端点值
if(L==R){tree[P]=a[L];return;} //最底层的叶子节点
int mid=(L+R)>>1; //分治，折半
Build_Tree(Ls(P), L, mid);
Build_Tree(Rs(P), mid+1, R);
Get_Parent(P); //自下而上传递区间值
}
Build_Tree(Ls(P),L,mid); 与 BUild_Tree(Rs(P),mid+1,R); 和之前的 归并排序（点击查看）算法如出一辙，都指向了 分治 这种 折半 的思想。
区间查询
查询区间和
目标查询区间 [L_edge , R_edge]。查询递归到某个结点 P（P 的区间[L,R] ），有两种情况：
1）[L_edge , R_edge] 完全覆盖 [L , R] ，L_edge <= L <= R <= R_edge ，直接返回 P 值。
2）[L_edge , R_edge] 与 [L , R]部分覆盖，分别搜索左右子节点。
1、若L_edge < L，则继续递归左子树，如：目标查询区间是 [4,9] ,与结点2 [1,5]有重叠（4<5），则会继续向下递归，直到获取到节点5的值
2、若 R < R_edge ，则继续递归右子树。
int res=0;
int L_edge,R_edge; //要访问的区间端点
int Query(int P,int L,int R){ //父节点以及他的左右端点值
if(L_edge<=L && R<=R_edge) //[L_edge , R_edge] 完全覆盖 [L , R]
return tree[P];
int mid=(L+R)>>1;
if(L_edge <= mid) res+=Query(Ls(P), L, mid); //L_edge 与 左子节点有重叠
if(R_edge > mid) res+=Query(Rs(P), mid+1, R); //R_edge 与 右子节点有重叠
}
Query(1,L_edge,R_edge); //函数调用
17-1-3 区间操作核心技术 Lazy_Tag
Lazy_Tag 叫 懒惰标记（或称为延迟标记）。
- 把 修改一个区间 看做 修改一个整体（当做整体的’单点修改’）的效率明显比 对区间每个数进行单点修改 要高很多。
Lazy_Tag 就采用了如上所述的 整体的'单点修改'：定义一个 Tag[i] 对 节点 i（区间）这个整体共同执行的加减操作进行记录（体现了一致性）
区间维护（修改）
把 【4,9】区间的每个元素加 3 ，步骤如下：
1）左子树递归到结点5（[4,5]）,完全包含在 [4,9] 内，对节点5打上标记 Tag[5] = 3，更新 Tree[5] = 20 ；
2）左子树递归向上，更新 Tree[2] = 30 ；
3）右子树递归到结点6（[6,8]）,标记Tag[6] = 3，更新 Tree[6] = 23；
4）右子树递归到结点14（[9,9]）,标记Tag[14] = 3，更新 Tree[14] = 13 、 返回后更新 Tree[7] = 20；
5）左右子节点合并更新 Tree[3] = 43 ，再合并后更新 Tree[1] = 73。
HDU 3372：线段树的 区间修改 以及 区间查询
#include<bits/stdc++.h>
using namespace std;
using LL=long long int;
const int N=1E5+5;
const int MAX=4*N;
struct node{ //待输入的参数
int L_edge;
int R_edge;
int d; //区间上每个元素共同的增量
//node(){}//默认构造函数：完成对象的默认初始化
/*自定义构造函数*/
//node(int l,int r,int d){this->L_edge=l,this->R_edge=r,this->d=d;}
node(int l,int r,int d):L_edge(l),R_edge(r),d(d){}//有参构造
//node():L_edge(),R_edge(),d(){}//无参数的构造函数数组初始化时调用
};
//能不经初始化就定义变量
int t=1; //修改次数的编号
vector<int> a(N,0); //规定：队列从下标1开始存储
vector<LL> tree(N<<2,0); //树段上的区间和
vector<int> tag(N<<2,0); //记录统一修改
/*--------------------树的构成--------------------------*/
int ls(int id){return id<<1;} //获取左子节点的编号 id*2
int rs(int id){return id<<1|1;} //获取左子节点的编号 id*2+1
void Get_Parent(int p){
tree[p]=tree[ls(p)] + tree[rs(p)]; //（自下而上）合并左右子节点的区间和
}
/*--------------------线段树的建立----------------------*/
void Build_Tree(int p,int L,int R){ //父节点以及他的左右端点值
if(L==R){tree[p]=a[L];return;} //当左右端点相等时就是（最底层的）叶子节点
int mid=(L+R)>>1; //分治思想：折半查找
Build_Tree(ls(p), L, mid); //（向下递归）左子节点
Build_Tree(rs(p), mid+1, R); //（向下递归）右子节点
Get_Parent(p); //（自下而上）传递区间值
}
/*-------------------对线段树的操作---------------------*/
void Tag_And_Update(int p,int L,int R,int d){
tag[p] += d; //打上tag
tree[p]+= d*(R-L+1); //更新节点值（区间和）
}
void Push_Tag_Down(int p,int L,int R){ //将tag标记传至
if(tag[p]){
int mid=(L+R)>>1;
Tag_And_Update(ls(p), L, mid,tag[p]); //tag标记传给左子树
Tag_And_Update(rs(p), mid+1, R,tag[p]); //tag标记传给右子树
tag[p]=0; //向下传递过后将tag归零
}
}
void Updata(int p,int L,int R,struct node n){
if(n.L_edge<=L && R<=n.R_edge){ //能完全覆盖就无需递归
Tag_And_Update(p,L,R,n.d);
return;
}
Push_Tag_Down(p,L,R);
int mid=(L+R)>>1;
if(n.L_edge <= mid)
Updata(ls(p), L, mid, n); //L_edge 与 左子节点有重叠
if(n.R_edge > mid)
Updata(rs(p), mid+1, R, n); //R_edge 与 右子节点有重叠
Get_Parent(p);
}
/*-------------------对线段树的节点的查询-----------------*/
LL Query(int p,int L,int R,struct node n){
if(n.L_edge<=L && R<=n.R_edge) //[L_edge , R_edge] 完全覆盖 [L , R]
return tree[p];
Push_Tag_Down(p,L,R); //不能覆盖则递归
int mid=(L+R)>>1;
LL res=0;
if(n.L_edge <= mid) //L_edge 与 左子节点有重叠
res+=Query(ls(p), L, mid,n);
if(n.R_edge > mid) //R_edge 与 右子节点有重叠
res+=Query(rs(p), mid+1, R,n);
return res;
}
int main(void){
int n,m; scanf("%d %d",&n,&m); //数列的个数,修改的次数
for(int i=1;i<=n;i++) //按序输入数列
scanf(" %d",&a[i]);
Build_Tree(1,1,n);
while(t<=m){
int p=1;
int L,R,d; scanf("%d %d %d",&L,&R,&d);
struct node n_node(L,R,d);//赋值初始化：利用自定义构造函数
//struct node n_node{L,R,d};//赋值初始化：利用默认构造函数（结构体（或叫类）中默认构造函数可以省略不用写）
Updata(p,1,n,n_node);
cout<<Query(p,1,1,n_node);
}
return 0;
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
1
0- 0
已为社区贡献2条内容
所有评论(0)