刚学线段树然后全RE了，求大佬帮

Echordy @ 2023-04-22 09:52:15

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll a[N],tree[N<<2];
ll tag[N<<2];
ll ls(ll p) {return p << 1; }
ll rs(ll p) {return p << 1 | 1;}
void push_up(ll p)  {tree[p] = tree[ls(p)] + tree[rs(p)];}
void set_tree(ll p,ll pl,ll pr)
{
    tag[p] = 0;
    if(pl == pr)    {tree[p] = a[pl];   return;}
    ll mid = (pl + pr) >> 1;
    set_tree(ls(p), pl, mid);
    set_tree(rs(p), mid+1, pr);
    push_up(p);
}
void addtag(ll p, ll pl, ll pr, ll d)
{
    tag[p] = d;
    tree[p] += d * (pr-pl+1);
}
void push_down(ll p, ll pl, ll pr)
{
    if(tag[p]){
        ll mid = (pl + pr) >> 1;
        addtag(ls(p), pl, mid, tag[p]);
        addtag(rs(p), mid+1, pr, tag[p]);
        tag[p] = 0;
    }
}
void update(ll L, ll R, ll p, ll pl, ll pr, ll d)
{
    if(L <= pl && R >= pr){
        addtag(p, pl, pr, d);
        return;
    }
    push_down(p, pl, pr);
    ll mid = (pr + pl) >> 1;
    if(pr > mid)    update(L, R, rs(p), mid+1, pr, d);
    if(pl <= mid)   update(L, R, ls(p), pl, mid, d);
    push_up(p);
}
ll query(ll L, ll R, ll p, ll pl, ll pr)
{
    if(L <= pl && R >= pr)  return tree[p];
    push_down(p, pl, pr);
    ll res = 0;
    ll mid = (pl + pr) >> 1;
    if(L <= mid)    res += query(L, R, ls(p), pl, mid);
    if(R > mid)     res += query(L, R, rs(p), mid+1, pr);
    return res;
}
int main()
{
    ll n,m;    cin >> n >> m;
    for(ll i = 1; i <= n; i++) cin >> a[i];
    set_tree(1, 1, n);
    while (m--){
        int mode;   cin >> mode;
        if(mode == 1){
            ll x,y,k;  cin >> x >> y >> k;
            update(x, y, 1, 1, n, k);
        }
        if(mode == 2){
            ll x,y; cin >> x >> y;
            cout << query(x, y, 1, 1, n) << endl;
        }
    }
}

by liangbowen @ 2023-04-22 09:59:11

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll a[N],tree[N<<2];
ll tag[N<<2];
ll ls(ll p) {return p << 1; }
ll rs(ll p) {return p << 1 | 1;}
void push_up(ll p)  {tree[p] = tree[ls(p)] + tree[rs(p)];}
void set_tree(ll p,ll pl,ll pr)
{
    tag[p] = 0;
    if(pl == pr)    {tree[p] = a[pl];   return;}
    ll mid = (pl + pr) >> 1;
    set_tree(ls(p), pl, mid);
    set_tree(rs(p), mid+1, pr);
    push_up(p);
}
void addtag(ll p, ll pl, ll pr, ll d)
{
    tag[p] += d;
    tree[p] += d * (pr-pl+1);
}
void push_down(ll p, ll pl, ll pr)
{
    if(tag[p]){
        ll mid = (pl + pr) >> 1;
        addtag(ls(p), pl, mid, tag[p]);
        addtag(rs(p), mid+1, pr, tag[p]);
        tag[p] = 0;
    }
}
void update(ll L, ll R, ll p, ll pl, ll pr, ll d)
{
    if(L <= pl && R >= pr){
        addtag(p, pl, pr, d);
        return;
    }
    push_down(p, pl, pr);
    ll mid = (pr + pl) >> 1;
    if(R > mid)    update(L, R, rs(p), mid+1, pr, d);
    if(L <= mid)   update(L, R, ls(p), pl, mid, d);
    push_up(p);
}
ll query(ll L, ll R, ll p, ll pl, ll pr)
{
    if(L <= pl && R >= pr)  return tree[p];
    push_down(p, pl, pr);
    ll res = 0;
    ll mid = (pl + pr) >> 1;
    if(L <= mid)    res += query(L, R, ls(p), pl, mid);
    if(R > mid)     res += query(L, R, rs(p), mid+1, pr);
    return res;
}
int main()
{
    ll n,m;    cin >> n >> m;
    for(ll i = 1; i <= n; i++) cin >> a[i];
    set_tree(1, 1, n);
    while (m--){
        int mode;   cin >> mode;
        if(mode == 1){
            ll x,y,k;  cin >> x >> y >> k;
            update(x, y, 1, 1, n, k);
        }
        if(mode == 2){
            ll x,y; cin >> x >> y;
            cout << query(x, y, 1, 1, n) << endl;
        }
    }
}

by liangbowen @ 2023-04-22 10:00:48

@Vanishsss \operatorname{addtag}() 是 tag[p] += d，然后 \operatorname{update}() 里面的分治是和 L, R 比较，而不是 pl, pr，原因显然

by Echordy @ 2023-04-23 10:25:00

@liangbowen 谢谢谢谢！ac了 还有就是为什么这样会RE啊??

by liangbowen @ 2023-04-23 12:14:13

@Vanishsss pos会以指数级增长，所以很快就会超过数组大小，自然re了