/*
	Name: Segment Tree
	Copyright: 22/08/24 ~ 22/08/25
	Author: Gcc_Gdb_7_8_1
	Date: 22/08/24 12:17
	Description: P3372
*/
#include <cstdio>
#define lson(x) ((x) << 1)
#define rson(x) (((x) << 1) | 1)
#define len(x) (tree[x].right - tree[x].left + 1)
#define to(x, y) ((y) - (x) + 1)
#define mid(l, r) (((l) + (r)) >> 1)
#define mian main
#define viod void
#define ture true
#define flase false
typedef long long LL;

constexpr int MAXN = 1e5 + 10;

struct Node
{
	int left = 0, right = 0;
	LL value = 0LL, lazy = 0LL;
} tree[MAXN << 2];

LL a[MAXN];

viod build(int st, int en, int n) { // 构建线段树
	tree[n].left = st;
	tree[n].right = en;
	if (st == en) {
		tree[n].value = a[st];
		return ;
	}
	int mi = mid(st, en);
	build(st, mi, lson(n));
	build(mi + 1, en, rson(n));
	tree[n].value = tree[lson(n)].value + tree[rson(n)].value;
}

viod pushup(int n) { // 上传值
    tree[n].value = tree[lson(n)].value + tree[rson(n)].value;
}

void pushdown(int n){ // 下发lazy标记
    if (tree[n].lazy){
        tree[lson(n)].lazy  += tree[n].lazy;
        tree[rson(n)].lazy  += tree[n].lazy;
        tree[lson(n)].value += tree[n].lazy * len(lson(n));
        tree[rson(n)].value += tree[n].lazy * len(rson(n));
        tree[n].lazy = 0;
    }
}

viod update(int l, int r, int st, int en, int n, LL k) { // 将 [x, y]
	if (l <= st && en <= r) {
		tree[n].value += to(st, en) * k;
		tree[n].lazy  += k;
		return ;
	}
	int mi = mid(st, en);
	if (tree[n].lazy && st != en) {
		pushdown(n);
	}
	if (l <= mi) {
		update(l, r, st, mi, lson(n), k);
	}
	if (r > mi) {
		update(l, r, mi + 1, en, rson(n), k);
	}
	pushup(n);
}

LL query(int l, int r, int st, int en, int n) {
	if (l <= st && en <= r) {
		return tree[n].value;
	}
	int mi = mid(st, en);
	if (tree[n].lazy) {
		pushdown(n);
	}
	LL ans = 0;
	if (l <= mi) {
		ans = query(l, r, st, mi, lson(n));
	}
	if (r > mi) {
		ans += query(l, r, mi + 1, en, rson(n));
	}
	return ans;
}

int mian()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	build(1, n, 1);
	while (m--) {
		int op, x, y;
		scanf("%d%d%d", &op, &x, &y);
		if (op == 1) {
		    LL k;
		    scanf("%lld", &k);
			update(x, y, 1, n, 1, k);
		} else {
			printf("%lld\n", query(x, y, 1, n, 1));
		}
	}
    return 0;
}

你康下这 update 和 pushdown 像吗（逻辑上）

@Ew_Cors 那也是log的啊

@little_zxh_qwq 姐姐看我的qwq

@little_zxh_qwq log 个毛线啊，你真的在认真算时间复杂度吗

@little_zxh_qwq 看我的 update 和 pushdown（把 viod 换成 void，我整活）

@Ew_Cors最多传树的深度次为什么不是log

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+5;
int a[MAXN];
int sgt[MAXN];
int lc[MAXN*4],rc[MAXN*4];
int tag[MAXN*4];
void pushdown(int i){
	if(tag[i]){
		sgt[i<<1]+=tag[i]*(rc[i<<1]-lc[i<<1]+1);
		sgt[(i<<1)|1]+=tag[i]*(rc[(i<<1)|1]-lc[(i<<1)|1]+1);
		tag[i<<1]+=tag[i];
		tag[(i<<1)|1]+=tag[i];
		tag[i]=0;
	}
}
void build(int l,int r,int i){
	lc[i]=l;
	rc[i]=r;
	if(l==r){
		sgt[i]=a[l];
		return;
	}
	int m=(l+r)>>1;
	build(l,m,i<<1);
	build(m+1,r,(i<<1)|1);
	sgt[i]=sgt[i<<1]+sgt[(i<<1)|1];
}

void update(int l,int r,int i,int x){
	if(l<=lc[i]&&rc[i]<=r){
		sgt[i]+=x*(rc[i]-lc[i]+1);
		tag[i]+=x;
		return;
	}
	pushdown(i);
	int m=(lc[i]+rc[i])>>1;
	if(l<=m) update(l,r,i<<1,x);
	if(r>m) update(l,r,(i<<1)|1,x);
	sgt[i]=sgt[i<<1]+sgt[(i<<1)|1];
}
int query(int l,int r,int i){
	if(l<=lc[i]&&rc[i]<=r){
		return sgt[i];
	}
	pushdown(i);
	int m=(lc[i]+rc[i])>>1;
	int sum=0;
	if(l<=m) sum+=query(l,r,i<<1);
	if(r>m) sum+=query(l,r,(i<<1)|1);
	return sum;
}
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int op,l,r;
		cin>>op>>l>>r;
		if(op==1){
			int x;
			cin>>x;
			update(l,r,1,x);
		}else{
			cout<<query(l,r,1)<<endl;
		}
	}
	return 0;
}

你每次 pushdown 都可以卡到 pushdown 每一个节点，单次查询不就变成 O(n) 的了

先别说我的写法，我函数名乱起的，能不能指出这个代码最根本的错误在哪里，谢谢

@little_zxh_qwq pushdown下面第一个if我写的是这个

if(x<=tree[r].lb && tree[r].rb<=y)
	{
		tree[r].lazy+=d;
		return;
	}
	tree[r].s+=(min(tree[r].rb,y)-max(tree[r].lb,x)+1)*d;

x是l，y是r，d是x，lbrb是lcrc