#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
struct tree{
	int l,r,sum,tag;
} tr[N*4];
int n,a[N],q,op,x,y,z;
void up(int p){
	tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
}
void down(int p){
	if(!tr[p].tag) return;
	tr[p<<1].sum+=(tr[p<<1].r-tr[p<<1].l+1)*tr[p].tag;
	tr[p<<1].tag+=tr[p].tag;
	tr[p<<1|1].sum+=(tr[p<<1|1].r-tr[p<<1|1].l+1)*tr[p].tag;
	tr[p<<1|1].tag+=tr[p].tag;
	tr[p].tag=0;
}
void build(int l,int r,int p){
	// 左端点命名为 l，右端点 r，块的下标为 p。 
	tr[p].l=l,tr[p].r=r;
	if(l==r){
		tr[p].sum=a[l];
		return;
	}
	int mid=tr[p].l+tr[p].r>>1;
	build(l,mid,p<<1),build(mid+1,r,p<<1|1);
	up(p);
}
void update(int l,int r,int p,int k){
	// update [l,r]区间加上k 
	if(tr[p].l==l&&tr[p].r==r){
		tr[p].sum+=(r-l+1)*k;
		tr[p].tag+=k;
		return;
	}
	down(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(l>mid) update(l,r,p<<1|1,k);
	else if(r<=mid) update(l,r,p<<1,k);
	else update(l,mid,p<<1,k),update(mid+1,r,p<<1|1,k);
	up(p);
}
int query(int l,int r,int p){ 
	// 查询的左端点 l ，查询的右端点是 r，块的下标为 p。 
	if(tr[p].l==l&&tr[p].r==r)
		return tr[p].sum;
	down(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(l>mid) return query(l,r,p<<1|1);
	else if(r<=mid) return query(l,r,p<<1);
	else return query(l,mid,p<<1)+query(mid+1,r,p<<1|1);
}
signed main(){
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	build(1,n,1);
	while(q--){
		scanf("%lld",&op);
		if(op==1){
			scanf("%lld%lld%lld",&x,&y,&z);
			update(x,y,1,z);
		} else{
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",query(x,y,1));
		}
	}
	return 0;
}

16 条评论

  • @ 2026-7-30 22:43:21

    \o/

    • @ 2026-7-17 11:13:06

      ber

      • @ 2026-7-17 11:10:00 
        #include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e5+5;//总结点数 
struct tree {
	int l,r,sum,tag;//l=左区间,r=右区间,sum=区间值,tag=懒标记 
} tr[N*4];//要开总结点数四倍 
int n,q,a[N];

//收集函数 
void up(int p){//p=收集祖节点下标 
	tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;//收集值 
}

//懒标记函数 
void down(int p){//p=懒标记下标 
	if (!tr[p].tag){
		return;
	}
	///分发值+懒标记///
	tr[p<<1].sum+=(tr[p<<1].r-tr[p<<1].l+1)*tr[p].tag;
	tr[p<<1].tag+=tr[p].tag;
	tr[p<<1|1].sum+=(tr[p<<1|1].r-tr[p<<1|1].l+1)*tr[p].tag;
	tr[p<<1|1].tag+=tr[p].tag;
	/////////////////// 
	tr[p].tag=0;//清零懒标记 
}

//构造线段树函数
void build(int l,int r,int p) { //l为查询左端点,r为查询左端点,p为本下标
	tr[p].l=l;
	tr[p].r=r;
	if (l==r) { //相等区间直接构造
		tr[p].sum=a[l];//赋值 
		return;
	}
	int mid=l+r>>1;//取中点
	build(l,mid,p<<1),build(mid+1,r,p<<1|1);//构造左与右区间
	up(p);//获取本区间的值
}

//增加某个区间值的函数 
void update(int l,int r,int p,int k) {//l为查询左端点,r为查询左端点,p为本下标,k为加的值 
	if (tr[p].l==l && tr[p].r==r) {//区间完全重合 
		tr[p].sum+=(r-l+1)*k;//加上k 
		tr[p].tag+=k;//懒标记记得也需要加上k
		return;
	}
	down(p);//懒标记 
	int mid=tr[p].l+tr[p].r>>1;//取中点
	if (l>mid) {
		update(l,r,p<<1|1,k);//如果都在左边
	} else if(r<=mid) {
		update(l,r,p<<1,k);//如果都在右边
	} else {
		update(l,mid,p<<1,k),update(mid+1,r,p<<1|1,k);//如果两边都有
	}
	up(p);//获取本区间的值
}

//查询区间函数
int query(int l,int r,int p) { //l为查询左端点,r为查询左端点,p为本下标
	if (tr[p].l==l && tr[p].r==r) {
		return tr[p].sum;//返回区间值 
	}
	down(p);//懒标记 
	int mid=tr[p].l+tr[p].r>>1;//取中点
	if (l>mid) {
		return query(l,r,p<<1|1);//如果都在左边
	} else if(r<=mid) {
		return query(l,r,p<<1);//如果都在右边
	} else {
		return query(l,mid,p<<1)+query(mid+1,r,p<<1|1);//如果两边都有
	}
}
signed main() {
	cin>>n>>q;//n节点数量,q操作数量 
	for (int i=1; i<=n; i++) {
		cin>>a[i];//每个节点值 
	}
	build(1,n,1);//创建线段树 
	int op;//操作 
	int x,y,z;
	while (q-- && cin>>op){
		if (op==1){
			cin>>x>>y>>z;
			update(x,y,1,z);//将x至y加上z; 
		}
		else{
			cin>>x>>y;
			cout<<query(x,y,1)<<'\n';//输出x至y的区间值 
		}
	}
}
        • @ 2026-7-17 11:09:28

          @欧拉班，线段树你们会吗 @图灵班，线段树你们会吗 @欧拉班，线段树你们会吗 @里奇班，线段树你们会吗

          • @ 2026-7-17 11:08:30

            @里奇班，线段树你们会吗

          • @ 2026-7-17 11:08:07

            图灵班的进来

            • @ 2026-7-17 11:07:42

              @高斯班，线段树你们会吗

            • @ 2026-7-17 11:07:41

              线段树

              #include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+10;
struct tree {
    int l,r,sum,tag;
} tr[N*4];
int a[N],n,m,op,x,y,z;
void up(int p) {
    tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;
}
void down(int p) {
    if (!tr[p].tag) return;
    tr[p << 1].sum += (tr[p << 1].r - tr[p<<1].l + 1) * tr[p].tag;
    tr[p << 1].tag += tr[p].tag;
    tr[p << 1 | 1].sum += (tr[p << 1|1].r - tr[p<<1|1].l + 1) * tr[p].tag;
    tr[p << 1 | 1].tag += tr[p].tag;
    tr[p].tag = 0;
}
void build(int l,int r,int p) {
    tr[p].l = l,tr[p].r = r;
    if (l == r) {
        tr[p].sum = a[l];
        return;
    }
    int mid = tr[p].l + tr[p].r >> 1;
    build(l,mid,p << 1);
    build(mid+1,r,p << 1 | 1);
    up(p);
}
void update(int l,int r,int p,int k) {
    if (tr[p].l == l && tr[p].r == r) {
        tr[p].sum += (r - l + 1) * k;
        tr[p].tag += k;
        return;
    }
    down(p);
    int mid = tr[p].l + tr[p].r >> 1;
    if (l > mid) update(l,r,p << 1|1,k);
    else if (r <= mid) update(l,r,p << 1,k);
    else update(l,mid,p << 1,k),update(mid+1,r,p << 1 | 1,k);
    tr[p].sum += tr[p << 1].sum + tr[p << 1 | 1].sum;
	up(p) ;
}
int query(int l,int r,int p) {
    if (tr[p].l == l && tr[p].r == r) {
        return tr[p].sum;
    }
	down(p) ;
    int mid = tr[p].l + tr[p].r >> 1;
    if (l > mid) return query(l,r,p << 1 | 1);
    else if (r <= mid) return query(l,r,p << 1);
    else return query(l,mid,p << 1) + query(mid+1,r,p << 1 | 1);
}
signed main() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    build(1,n,1);
    while (m--) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> z;
            update(x,y,1,z);
        } else {
            cin >> x >> y;
            cout << query(x,y,1) << endl;
        }
    }
    return 0;
}// 一个线段树模版！
              • @ 2026-7-17 11:07:22

                @欧拉班，线段树你们会吗

              • @ 2026-7-17 11:07:19

                吓哭了

                • @ 2026-7-17 11:07:15 
                  #include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+10;
struct tree {
    int l,r,sum,tag;
} tr[N*4];
int a[N],n,m,op,x,y,z;
void up(int p) {
    tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;
}
void down(int p) {
    if (!tr[p].tag) return;
    tr[p << 1].sum += (tr[p << 1].r - tr[p<<1].l + 1) * tr[p].tag;
    tr[p << 1].tag += tr[p].tag;
    tr[p << 1 | 1].sum += (tr[p << 1|1].r - tr[p<<1|1].l + 1) * tr[p].tag;
    tr[p << 1 | 1].tag += tr[p].tag;
    tr[p].tag = 0;
}
void build(int l,int r,int p) {
    tr[p].l = l,tr[p].r = r;
    if (l == r) {
        tr[p].sum = a[l];
        return;
    }
    int mid = tr[p].l + tr[p].r >> 1;
    build(l,mid,p << 1);
    build(mid+1,r,p << 1 | 1);
    up(p);
}
void update(int l,int r,int p,int k) {
    if (tr[p].l == l && tr[p].r == r) {
        tr[p].sum += (r - l + 1) * k;
        tr[p].tag += k;
        return;
    }
    down(p);
    int mid = tr[p].l + tr[p].r >> 1;
    if (l > mid) update(l,r,p << 1|1,k);
    else if (r <= mid) update(l,r,p << 1,k);
    else update(l,mid,p << 1,k),update(mid+1,r,p << 1 | 1,k);
    tr[p].sum += tr[p << 1].sum + tr[p << 1 | 1].sum;
	up(p) ;
}
int query(int l,int r,int p) {
    if (tr[p].l == l && tr[p].r == r) {
        return tr[p].sum;
    }
	down(p) ;
    int mid = tr[p].l + tr[p].r >> 1;
    if (l > mid) return query(l,r,p << 1 | 1);
    else if (r <= mid) return query(l,r,p << 1);
    else return query(l,mid,p << 1) + query(mid+1,r,p << 1 | 1);
}
signed main() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    build(1,n,1);
    while (m--) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> z;
            update(x,y,1,z);
        } else {
            cin >> x >> y;
            cout << query(x,y,1) << endl;
        }
    }
}
                  • @ 2026-7-17 11:06:19

                    wwwww

                    • @ 2026-7-17 11:06:19 
                      #include <bits/stdc++.h>

#pragma GCC optimize(3,"Ofast","inline")
typedef long long ll;
#define endl "\n"
#define int long long
using namespace std;
const int N = 1e5+10;
struct tree {
    int l,r,sum,tag;
} tr[N*4];
int a[N],n,m,op,x,y,z;
void up(int p) {
    tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;
}
void down(int p) {
    if (!tr[p].tag) return;
    tr[p << 1].sum += (tr[p << 1].r - tr[p << 1].l + 1) * tr[p].tag;
    tr[p << 1].tag += tr[p].tag;
    tr[p << 1 | 1].sum += (tr[p << 1 | 1].r - tr[p << 1 | 1].l + 1) * tr[p].tag;
    tr[p << 1 | 1].tag += tr[p].tag;
    tr[p].tag = 0;
}
void build(int l,int r,int p) {
    tr[p].l = l,tr[p].r = r;
    if (l == r) {
        tr[p].sum = a[l];
        return;
    }
    int mid = tr[p].l + tr[p].r >> 1;
    build(l,mid,p << 1);
    build(mid+1,r,p << 1 | 1);
    up(p);
}
void update(int l,int r,int p,int k) {
    if (tr[p].l == l && tr[p].r == r) {
        tr[p].sum += (r - l + 1) * k;
        tr[p].tag += k;
        return;
    }
    down(p);
    int mid = tr[p].l + tr[p].r >> 1;
    if (l > mid) update(l,r,p << 1 | 1,k);
    else if (r <= mid) update(l,r,p << 1,k);
    else update(l,mid,p << 1,k),update(mid+1,r,p << 1 | 1,k);
    up(p);
}
int query(int l,int r,int p) {
    if (tr[p].l == l && tr[p].r == r) {
        return tr[p].sum;
    }
    down(p);
    int mid = tr[p].l + tr[p].r >> 1;
    if (l > mid) return query(l,r,p << 1 | 1);
    else if (r <= mid) return query(l,r,p << 1);
    else return query(l,mid,p << 1) + query(mid+1,r,p << 1 | 1);
}
signed main() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    build(1,n,1);
    while (m--) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> z;
            update(x,y,1,z);
        } else {
            cin >> x >> y;
            cout << query(x,y,1) << endl;
        }
    }
    return 0;
}
                      • @ 2026-7-17 11:06:07

                        @图灵班，线段树你们会吗

                      • @ 2026-7-17 11:04:48 
                        #include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e5+5;//总结点数 
struct tree {
	int l,r,sum,tag;//l=左区间,r=右区间,sum=区间值,tag=懒标记 
} tr[N*4];//要开总结点数四倍 
int n,q,a[N];

//收集函数 
void up(int p){//p=收集祖节点下标 
	tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;//收集值 
}

//懒标记函数 
void down(int p){//p=懒标记下标 
	if (!tr[p].tag){
		return;
	}
	///分发值+懒标记///
	tr[p<<1].sum+=(tr[p<<1].r-tr[p<<1].l+1)*tr[p].tag;
	tr[p<<1].tag+=tr[p].tag;
	tr[p<<1|1].sum+=(tr[p<<1|1].r-tr[p<<1|1].l+1)*tr[p].tag;
	tr[p<<1|1].tag+=tr[p].tag;
	/////////////////// 
	tr[p].tag=0;//清零懒标记 
}

//构造线段树函数
void build(int l,int r,int p) { //l为查询左端点,r为查询左端点,p为本下标
	tr[p].l=l;
	tr[p].r=r;
	if (l==r) { //相等区间直接构造
		tr[p].sum=a[l];//赋值 
		return;
	}
	int mid=l+r>>1;//取中点
	build(l,mid,p<<1),build(mid+1,r,p<<1|1);//构造左与右区间
	up(p);//获取本区间的值
}

//增加某个区间值的函数 
void update(int l,int r,int p,int k) {//l为查询左端点,r为查询左端点,p为本下标,k为加的值 
	if (tr[p].l==l && tr[p].r==r) {//区间完全重合 
		tr[p].sum+=(r-l+1)*k;//加上k 
		tr[p].tag+=k;//懒标记记得也需要加上k
		return;
	}
	down(p);//懒标记 
	int mid=tr[p].l+tr[p].r>>1;//取中点
	if (l>mid) {
		update(l,r,p<<1|1,k);//如果都在左边
	} else if(r<=mid) {
		update(l,r,p<<1,k);//如果都在右边
	} else {
		update(l,mid,p<<1,k),update(mid+1,r,p<<1|1,k);//如果两边都有
	}
	up(p);//获取本区间的值
}

//查询区间函数
int query(int l,int r,int p) { //l为查询左端点,r为查询左端点,p为本下标
	if (tr[p].l==l && tr[p].r==r) {
		return tr[p].sum;//返回区间值 
	}
	down(p);//懒标记 
	int mid=tr[p].l+tr[p].r>>1;//取中点
	if (l>mid) {
		return query(l,r,p<<1|1);//如果都在左边
	} else if(r<=mid) {
		return query(l,r,p<<1);//如果都在右边
	} else {
		return query(l,mid,p<<1)+query(mid+1,r,p<<1|1);//如果两边都有
	}
}
signed main() {
	cin>>n>>q;//n节点数量,q操作数量 
	for (int i=1; i<=n; i++) {
		cin>>a[i];//每个节点值 
	}
	build(1,n,1);//创建线段树 
	int op;//操作 
	int x,y,z;
	while (q-- && cin>>op){
		if (op==1){
			cin>>x>>y>>z;
			update(x,y,1,z);//将x至y加上z; 
		}
		else{
			cin>>x>>y;
			cout<<query(x,y,1)<<'\n';//输出x至y的区间值 
		}
	}
}
                        🤔 1
                        • @ 2026-7-17 11:04:34

                          #include <bits/stdc++.h> using namespace std; #define int long long const int N=1e5+5;//总结点数 struct tree { int l,r,sum,tag;//l=左区间,r=右区间,sum=区间值,tag=懒标记 } tr[N*4];//要开总结点数四倍 int n,q,a[N];

                          //收集函数 void up(int p){//p=收集祖节点下标 tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;//收集值 }

                          //懒标记函数 void down(int p){//p=懒标记下标 if (!tr[p].tag){ return; } ///分发值+懒标记/// tr[p<<1].sum+=(tr[p<<1].r-tr[p<<1].l+1)*tr[p].tag; tr[p<<1].tag+=tr[p].tag; tr[p<<1|1].sum+=(tr[p<<1|1].r-tr[p<<1|1].l+1)*tr[p].tag; tr[p<<1|1].tag+=tr[p].tag; /////////////////// tr[p].tag=0;//清零懒标记 }

                          //构造线段树函数 void build(int l,int r,int p) { //l为查询左端点,r为查询左端点,p为本下标 tr[p].l=l; tr[p].r=r; if (l==r) { //相等区间直接构造 tr[p].sum=a[l];//赋值 return; } int mid=l+r>>1;//取中点 build(l,mid,p<<1),build(mid+1,r,p<<1|1);//构造左与右区间 up(p);//获取本区间的值 }

                          //增加某个区间值的函数 void update(int l,int r,int p,int k) {//l为查询左端点,r为查询左端点,p为本下标,k为加的值 if (tr[p].ll && tr[p].rr) {//区间完全重合 tr[p].sum+=(r-l+1)*k;//加上k tr[p].tag+=k;//懒标记记得也需要加上k return; } down(p);//懒标记 int mid=tr[p].l+tr[p].r>>1;//取中点 if (l>mid) { update(l,r,p<<1|1,k);//如果都在左边 } else if(r<=mid) { update(l,r,p<<1,k);//如果都在右边 } else { update(l,mid,p<<1,k),update(mid+1,r,p<<1|1,k);//如果两边都有 } up(p);//获取本区间的值 }

                          //查询区间函数 int query(int l,int r,int p) { //l为查询左端点,r为查询左端点,p为本下标 if (tr[p].ll && tr[p].rr) { return tr[p].sum;//返回区间值 } down(p);//懒标记 int mid=tr[p].l+tr[p].r>>1;//取中点 if (l>mid) { return query(l,r,p<<1|1);//如果都在左边 } else if(r<=mid) { return query(l,r,p<<1);//如果都在右边 } else { return query(l,mid,p<<1)+query(mid+1,r,p<<1|1);//如果两边都有 } } signed main() { cin>>n>>q;//n节点数量,q操作数量 for (int i=1; i<=n; i++) { cin>>a[i];//每个节点值 } build(1,n,1);//创建线段树 int op;//操作 int x,y,z; while (q-- && cin>>op){ if (op==1){ cin>>x>>y>>z; update(x,y,1,z);//将x至y加上z; } else{ cin>>x>>y; cout<<query(x,y,1)<<'\n';//输出x至y的区间值 } } }

                          • 1
                          33
                          已通过
                          0
                          题解被赞
                          1. Language
                          2. 主题
                          3. 关于
                          2. 粤ICP备19104337号   可达信奥官网   域
                          5. Powered by Hydro v5.0.4 Community