线段树的构建和单点修改
2026-08-21 19:47:50
发布于：浙江
7阅读
0回复
0点赞
void build(long long p,long long l,long long r){
//将左端点和右端点的数据放入p节点下
tree[p].l=l;
tree[p].r=r;
//当前是叶子节点，当左节点等同于右节点时，已经到达最后一层
if(l==r){
tree[p].value=arr[l];//放入值，放入arr[r]也是一个道理
return;//结束，退出之后就不执行了
}
int mid=(l+r)/2;
bulid(p*2,l,mid);
bulid(p*2+1,mid+1,r);
tree[p].value=tree[p*2].value+tree[p*2+1].value;
}
void update(long long p,long long x,long long z){
//找到需要查询的位置
if(tree[p].l==tree[p].r){
//对于找到的位置进行修改（给x的位置增加）
tree[p].value+=z;
return;
}
//二分范围
int mid=(tree[p].l+tree[p].r)/2;//左右划分
//如果需要修改的左半边范围正好包含
if(x<=mid){
update(p*2,x,z);
}else if(x>mid){//如果需要修改的右半边范围正好包含
update(p*2+1,x,z);
}
tree[p].value=tree[p*2].value+tree[p*2+1].value;//回溯
}
long long query(long long p,int x,int y){
//需要查询的范围包含了p下标的所有
if(x<=tree[p].l&&y>=tree[p].r){
//范围p下标包含的值
return tree[p].value;
}
int mid=(tree[p].l+tree[p].r)/2;//二分范围
long long flag=0;//记录总和
if(x<=mid){
flag+=query(p*2,x,y);//去左子树
}
if(y>mid){
flag+=query(p*2+1,x,y);//去右子树
}
return flag;
}
下面是例题的代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,k,arr[1000010];
struct node{
long long l,r,value;
};
node tree[4000040];
void build(long long p,long long l,long long r){
tree[p].l=l;
tree[p].r=r;
if(l==r){
tree[p].value=arr[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tree[p].value=tree[p*2].value+tree[p*2+1].value;
}
void update(long long p,long long x,long long z){
if(tree[p].l==tree[p].r){
tree[p].value+=z;
return ;
}
int mid=(tree[p].l+tree[p].r)/2;
if(x<=mid){
update(p*2,x,z);
}else if(x>mid){
update(p*2+1,x,z);
}
tree[p].value=tree[p*2].value+tree[p*2+1].value;
}
long long query(long long p,int x,int y){
if(x<=tree[p].l&&y>=tree[p].r){
return tree[p].value;
}
int mid=(tree[p].l+tree[p].r)/2;
long long flag=0;
if(x<=mid){
flag+=query(p*2,x,y);
}
if(y>mid){
flag+=query(p*2+1,x,y);
}
return flag;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
build(1,1,n);
for(int i=1;i<=m;i++){
int x;
cin>>x;
if(x==1){
int a,b;
cin>>a>>b;
update(1,a,b);
}else{
int a,b;
cin>>a>>b;
cout<<query(1,a,b)<<endl;
}
}
return 0;
}
这里空空如也
有帮助，赞一个