刚学线段树...求调....

Stevehim @ 2022-11-02 23:34:41

#include <bits/stdc++.h>
#define maxn 1000000
using namespace std;
typedef unsigned long long ull;
struct node {
    int l;
    int r;
    ull val;
    ull add;
} a[maxn];
int num[maxn];
int n,m;
void build(int l,int r,int p) { //建树操作
    a[p].l = l;
    a[p].r = r;
    if(l == r) {
        a[p].val = num[p];
        return;
    }
    int mid = (l + r) / 2;
    build(l,mid,2 * p); //为什么：因为建的是左子树，所以传l
    build(mid+1,r, 2 * p + 1);
    a[p].val = a[2 * p].val + a[2 * p + 1].val;
}

void spread(int p) {
    if(a[p].add) {
        a[p * 2].val += a[p].add * (a[p*2].r - a[p*2].l + 1); //将所有区间的值全部修了
        a[p*2+1].val += a[p].add * (a[p*2+1].r - a[p*2+1].l + 1);
        a[p*2].add+=a[p].add;
        a[p*2+1].add+=a[p].add;
        a[p].add=0;
    }
}

void change(int l,int r,int p,int z) {
    if(l <= a[p].l && r >= a[p].r) { //已经包括了这段区间
        a[p].val += (ull)z*(a[p].r-a[p].l +1);
        a[p].add += z;
        return;
    }
    spread(p);//先进行一次下传操作
    int mid = (a[p].l + a[p].r) / 2;
    if(r <= mid) {
        change(l,r,p*2,z);
    }
    if(l > mid) {
        change(l,r,p*2+1,z);
    }
    a[p].val = a[p*2].val+a[p*2+1].val;
}

ull ask(int l, int r,int p) {

    if(l <= a[p].l && r >= a[p].r) {
        return a[p].val;
    }
    spread(p);
    ull ans = 0;
    int mid = (a[p].l + a[p].r) / 2;
    if(l <= mid) {
        ans += ask(l,r,p*2);
    }
    if(r > mid) {
        ans += ask(l,r,p*2+1);
    }
    return ans;
}

int main() {
    cin >>n >>m;
    for(int i = 1; i <= n; i++) {
        cin >>num[i];
    }
    build(1,n,1);
    int op;
    int x,y,k;
    for(int i = 0 ; i< m; i++) {
        cin >> op;
        if(op == 1) {
            cin >> x >> y >> k;
            change(x,y,1,k);
        } else {
            cin >> x >> y;
            cout << ask(x,y,1) << endl;
        }
    }
    return 0;
}

by NinT_W @ 2022-11-03 06:28:24

@Stevehim

#include <bits/stdc++.h>
#define maxn 1000000
using namespace std;
typedef unsigned long long ull;
struct node {
    int l;
    int r;
    ull val;
    ull add;
} a[maxn];
int num[maxn];
int n,m;
void build(int l,int r,int p) { //建树操作
    a[p].l = l;
    a[p].r = r;
    if(l == r) {
        a[p].val = num[l];//num[p];
        return;
    }
    int mid = (l + r) / 2;
    build(l,mid,2 * p); //为什么：因为建的是左子树，所以传l
    build(mid+1,r, 2 * p + 1);
    a[p].val = a[2 * p].val + a[2 * p + 1].val;
}

void spread(int p) {
    if(a[p].add) {
        a[p * 2].val += a[p].add * (a[p*2].r - a[p*2].l + 1); //将所有区间的值全部修了
        a[p*2+1].val += a[p].add * (a[p*2+1].r - a[p*2+1].l + 1);
        a[p*2].add+=a[p].add;
        a[p*2+1].add+=a[p].add;
        a[p].add=0;
    }
}

void change(int l,int r,int p,int z) {
    if(l <= a[p].l && r >= a[p].r) { //已经包括了这段区间
        a[p].val += (ull)z*(a[p].r-a[p].l +1);
        a[p].add += z;
        return;
    }
    spread(p);//先进行一次下传操作
    int mid = (a[p].l + a[p].r) / 2;
/*    if(r <= mid) {
        change(l,r,p*2,z);
    }
    if(l > mid) {
        change(l,r,p*2+1,z);
    }
*/
    if(l<=mid) change(l,r,p*2,z);
    if(r>mid) change(l,r,p*2+1,z);
  a[p].val = a[p*2].val+a[p*2+1].val;
}

ull ask(int l, int r,int p) {

    if(l <= a[p].l && r >= a[p].r) {
        return a[p].val;
    }
    spread(p);
    ull ans = 0;
    int mid = (a[p].l + a[p].r) / 2;
    if(l <= mid) {
        ans += ask(l,r,p*2);
    }
    if(r > mid) {
        ans += ask(l,r,p*2+1);
    }
    return ans;
}

int main() {
    cin >>n >>m;
    for(int i = 1; i <= n; i++) {
        cin >>num[i];
    }
    build(1,n,1);
    int op;
    int x,y,k;
    for(int i = 0 ; i< m; i++) {
        cin >> op;
        if(op == 1) {
            cin >> x >> y >> k;
            change(x,y,1,k);
        } else {
            cin >> x >> y;
            cout << ask(x,y,1) << endl;
        }
    }
    return 0;
}

这样就OK

by NinT_W @ 2022-11-03 06:58:00

17行build函数中初始值赋错力

44行到49行向下更新判断时有误

by Stevehim @ 2022-11-03 20:27:38

@NinT_W ！！！感谢 ！！！