树状数组写线段树写错了,求助

P3372 【模板】线段树 1

_FastFT2013 @ 2024-01-27 15:06:43

#include<iostream>
#define lowbit(x) (x&(-x))
using namespace std;
const int N=1e5+5;//原数组/树状数组最大长度 
template<typename T>
struct Tree_array{
    int s=0;
    T c[N]={0},ci[N]={0};
    void build(T a[],int n){//树状数组预处理(构造) O(n)
        s=n;
        T fa[n+5],qfa[n+5];
        for(int i=1;i<=n;i++){
            fa[i]=a[i]-a[i-1];
            fa[i]*=i;
            qfa[i]=qfa[i-1]+fa[i];
        }
        for(int i=1;i<=n;i++){
            ci[i]=qfa[i]-qfa[i-lowbit(i)];
            c[i]=a[i]-a[i-lowbit(i)];
        }
    }
    T find(int x){//单点查询(查询x节点的值) O(log n)
        T sum=0;
        for(int i=x;i;i-=lowbit(i))sum+=c[i];
        return sum;
    }
    void add_q(int x,int k){//区间修改(将x~n节中点的值加上k) O(log n) 
        for(int i=x;i<=s;i+=lowbit(i)){
            c[i]+=x;
            ci[i]+=x*k;
        }
    }
    void add_q(int x,int y,int k){//区间修改(将x~y中节点的值加上k) O(log n) 
        add_q(x,k),add_q(y+1,-k);
    }
    void add(int x,int k){//单点修改(将节点x加上k) O(log n) 
        add_q(x,x,k);
    }
    T find_q(int x){//区间查询(查询1~x中的和) O(log n)
        T sum1=0,sum2=0;
        for(int i=x;i;i-=lowbit(i))sum1+=c[i];
        sum1*=x+1;
        for(int i=x;i;i-=lowbit(i))sum2+=ci[i];
        return sum1-sum2;
    }
    T find_q(int x,int y){//区间查询(查询x~y的和) O(log n) 
        return find_q(y)-find_q(x-1);
    }
};
Tree_array<long long>tree;
long long a[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    tree.build(a,n);
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int x,y,k;
            cin>>x>>y>>k;
            tree.add_q(x,y,k);
        }else{
            int x,y;
            cin>>x>>y;
            cout<<tree.find_q(x,y)<<"\n";
        }
    }
    return 0;
}

by Super_Cube @ 2024-01-28 14:47:20

@wuxiuyuan 第 29 行:c[i]+=x 改为 c[i]+=k


by _FastFT2013 @ 2024-01-29 08:02:58

谢谢@Super_Cube


|