线段树
2026-02-22 11:22:00
发布于：浙江
18阅读
0回复
0点赞
这个代码是我根据我所学视频+我自己的理解编写而成的，是洛谷的线段树模板 。封装了。
#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 pushdowm(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;
pushdowm(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;
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;
pushdowm(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;
}
有帮助，赞一个