线段树
2026-02-24 16:35:09
发布于：浙江
45阅读
0回复
0点赞
这个代码是我根据我所学视频+我自己的理解编写而成的，是洛谷的线段树模板 。封装了。
这个单点更新函数好像有点si了，先用区间更新函数代替下把、
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=4000005;
vector<int> a(N);
class segment_tree{
private:
struct node{
int lazy=0,data;
}tree[N];
int left_child(int now){//取左孩子，返回的是索引
return 2*now;
}int right_child(int now){//取右孩子
return 2*now+1;
}void pushdown(int now,int l,int r){//懒标记的处理
if(tree[now].lazy!=0){
int mid=(l+r)/2;
tree[left_child(now)].data+=tree[now].lazy*(mid-l+1);
tree[left_child(now)].lazy+=tree[now].lazy;
tree[right_child(now)].data+=tree[now].lazy*(r-mid);
tree[right_child(now)].lazy+=tree[now].lazy;
tree[now].lazy=0;
}
}
public:
void build(int now,int l,int r){//递归建树
tree[now].lazy=0;//懒标记的初始化，后面会讲
if(l==r){//叶子节点
tree[now].data=a[l];
return ;
}int mid=l+(r-l)/2;
build(left_child(now),l,mid);build(right_child(now),mid+1,r);//分别递归左半边和右半边
tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;//赋值该节点为他的左右孩子节点值之和。
}
long long query_add(int now,int l,int r,int ql,int qr){//求区间和函数。分别为当前节点，左区间，右区间，所求区间的左右区间
if(ql>r or qr<l)return 0;
if(ql<=l and qr>=r)return tree[now].data;
int mid=l+(r-l)/2;
pushdown(now,l,r);
return query_add(left_child(now),l,mid,ql,qr)+query_add(right_child(now),mid+1,r,ql,qr);
}
void update(int now,int l,int r,int idx,int val){//单点更新
if(l==r){
tree[now].data=val;
return ;
}int mid=l+(r-l)/2;
pushdown(now,l,r);
if(idx<=mid){
update(left_child(now),l,mid,idx,val);
}else{
update(right_child(now),mid+1,r,idx,val);
}tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;
}
void update_range(int now,int l,int r,int ul,int ur,int val){//区间更新
if(ul>r or ur<l)return ;
if(ul<=l and ur>=r){
tree[now].data+=1LL*val*(r-l+1);
tree[now].lazy+=val;
return ;
}int mid=l+(r-l)/2;
pushdown(now,l,r);
update_range(left_child(now),l,mid,ul,ur,val);
update_range(right_child(now),mid+1,r,ul,ur,val);
tree[now].data=tree[left_child(now)].data+tree[right_child(now)].data;
}
};
signed main(){
segment_tree tree;
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> a[i];
}tree.build(1,1,n);
while(m--){
int op;
cin >> op;
if(op==1){
int x,y,k;
cin >> x >> y >> k;
tree.update_range(1,1,n,x,y,k);
}else{
int x,y;
cin >> x >> y;
cout << tree.query_add(1,1,n,x,y) << "\n";
}
}
return 0;
}
全部评论 6
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
6天前 来自 北京
0
有帮助，赞一个