线段树模板的一点不理解，问一下

萌田薰子 @ 2023-04-07 23:47:51

by Loic_ @ 2023-04-07 23:53:24

放代码。不放代码谁知道你哪里写错了。

by 萌田薰子 @ 2023-04-07 23:55:25

@Loic_ 大佬看看=w=

这是正确代码，在add函数里如果去掉了pushdown就会报错

#include <cstdio>
#define ll long long
#define N 100010
using namespace std;
int n,m,mode,i,j;
ll tr[N << 3],laz[N << 3],v[N],k;
void build(int l,int r,int len) {
    if (l == r) {tr[len] = v[r]; return;}
    int mid = (l + r) >> 1;
    build(l,mid,len << 1);
    build(mid + 1,r,len << 1 | 1);
    tr[len] = tr[len << 1] + tr[len << 1 | 1];
}
void pushdown(int x,int y,int leng) {
    if (!laz[leng]) return;
    int mid = (x + y) >> 1;
    tr[leng << 1] += laz[leng] * (mid - x + 1);
    tr[leng << 1 | 1] += laz[leng] * (y - mid);
    laz[leng << 1] += laz[leng];
    laz[leng << 1 | 1] += laz[leng];
    laz[leng] = 0;
}
void add(int l,int r,int len) {
    pushdown(l,r,len);
    if (i <= l && r <= j) {
        tr[len] += k * (r - l + 1);
        laz[len] += k;
        return;
    }
    int mid = (l + r) >> 1;
    if (i <= mid) add(l,mid,len << 1);
    if (mid < j) add(mid + 1,r,len << 1 | 1);
    tr[len] = tr[len << 1] + tr[len << 1 | 1];
}
ll sum(int l,int r,int len) {
    pushdown(l,r,len);
    if (i <= l && r <= j) return tr[len];
    ll bot = 0;
    int mid = (l + r) >> 1;
    if (i <= mid) bot += sum(l,mid,len << 1);
    if (mid < j) bot += sum(mid + 1,r,len << 1 | 1);
    return bot;
}
int main() {
    scanf("%d%d",&n,&m);
    for (int a = 1 ; a <= n ; ++ a) scanf("%lld",&v[a]);
    build(1,n,1);
    while (m--) {
        scanf("%d",&mode);
        if (mode == 1) scanf("%d%d%lld",&i,&j,&k),add(1,n,1); else
        scanf("%d%d",&i,&j),printf("%lld\n",sum(1,n,1));
    }
    return 0;
}

by lfxxx @ 2023-04-08 00:11:55

@萌田薰子 这是因为查询的到子节点的时候其父节点的标记可能还没有下传

by Loic_ @ 2023-04-08 00:12:27

感觉和 add 函数最后一句有关吧。不 pushdown 更新到上面和就是错的。

by 萌田薰子 @ 2023-04-08 00:28:17

@ChiFAN 查询的时候我都开头就调用了pushdown的，顺着儿子一直下去，应该不存在查询的时候没下传的问题吧，修改的时候倒确实是没下传

by lfxxx @ 2023-04-08 00:29:01

@Loic_ pushdown 不是下传标记吗

by lfxxx @ 2023-04-08 00:31:23

@萌田薰子 对，是因为修改的时候没有下传导致被修改的叶子结点的父节点的标记没了

by 萌田薰子 @ 2023-04-08 00:33:05

@Loic_ 我觉得，这最后一句是，对本次laz没影响到的上面所有区间值进行更新，之后修改也是对之后的未影响区间进行更新；

所以如果查询的区间是某次lazy上面的，那值早就更新过了；一旦查询要遍历到下面的区间，把lazy下放就能顺便更新下面的，上面的也没影响，下面的值也取的是更新后的，感觉没啥问题

但是就是有问题我才来问的x

by 萌田薰子 @ 2023-04-08 00:34:31

@ChiFAN 诶，不会没吧（

我修改的时候lazy是+=的，您还看出了什么蹊跷吗

by Loic_ @ 2023-04-08 00:38:43

@萌田薰子 修改不 pushdown Hack:

2 3
0 0
1 1 2 1
1 1 1 1
2 1 2

请自己想想为什么是这样。