树状数组

int n;
int a[1005],c[1005]; //对应原数组和树状数组

int lowbit(int x){
    return x&(-x);
}

void updata(int i,int k){    //在i位置加上k
    while(i <= n){
        c[i] += k;
        i += lowbit(i);
    }
}

int getsum(int i){        //求A[1 - i]的和
    int res = 0;
    while(i > 0){
        res += c[i];
        i -= lowbit(i);
    }
    return res;
}

 int n,m;
  int a[50005] = {0},c[50005]; //对应原数组和树状数组
  
  int lowbit(int x){
      return x&(-x);
  }
  
  void updata(int i,int k){    //在i位置加上k
      while(i <= n){
         c[i] += k;
         i += lowbit(i);
     }
 }
 
 int getsum(int i){        //求D[1 - i]的和，即A[i]值
     int res = 0;
     while(i > 0){
         res += c[i];
         i -= lowbit(i);
     }
     return res;
 }
 
 int main(){
     cin>>n;
     for(int i = 1; i <= n; i++){
         cin>>a[i];
         updata(i,a[i] - a[i-1]);   //输入初值的时候，也相当于更新了值
     }
     
     //[x,y]区间内加上k
     updata(x,k);    //A[x] - A[x-1]增加k
     updata(y+1,-k);        //A[y+1] - A[y]减少k
     
     //查询i位置的值
     int sum = getsum(i);
 
     return 0;
 }

int n,m;
int a[50005] = {0};
int sum1[50005];    //(D[1] + D[2] + ... + D[n])
int sum2[50005];    //(1*D[1] + 2*D[2] + ... + n*D[n])

int lowbit(int x){
    return x&(-x);
}

void updata(int i,int k){
    int x = i;    //因为x不变，所以得先保存i值
    while(i <= n){
        sum1[i] += k;
        sum2[i] += k * (x-1);
        i += lowbit(i);
    }
}

int getsum(int i){        //求前缀和
    int res = 0, x = i;
    while(i > 0){
        res += x * sum1[i] - sum2[i];
        i -= lowbit(i);
    }
    return res;
}

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        updata(i,a[i] - a[i-1]);   //输入初值的时候，也相当于更新了值
    }

    //[x,y]区间内加上k
    updata(x,k);    //A[x] - A[x-1]增加k
    updata(y+1,-k);        //A[y+1] - A[y]减少k

    //求[x,y]区间和
    int sum = getsum(y) - getsum(x-1);

    return 0;
}