CODEVS-1082树状数组改段求段模板

POJ4970:树状数组直接莽法: 传送门

/*
s[n] = n*(d1+..+dn)-(c1+...+cn)
c[i] = (i-1)*d[i]
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;
const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
LL bit[N], cit[N], ar[N], sum[N], pre[N];
int n, m, q;
void addb(int x, LL val){
  while(x<=n){
    bit[x] += val;
    x += lowbit(x);
  }
}
LL queryb(int x){
  LL tsum = 0;
  while(x>0){
    tsum += bit[x];
    x -= lowbit(x);
  }
  return tsum;
}
void addc(int x, LL val){
  while(x<=n){
    cit[x] += val;
    x += lowbit(x);
  }
}
LL queryc(int x){
  LL tsum = 0;
  while(x>0){
    tsum += cit[x];
    x -= lowbit(x);
  }
  return tsum;
}
LL allsum(int l,int r){
  return (r*queryb(r)-queryc(r))-((l-1)*queryb(l-1)-queryc(l-1));
}
int main(){
  int l, r, op;
  LL val;
  while(~scanf("%d", &n)&&n){
    scanf("%d",&m);
    for(int i =0;i<=n;++i)bit[i] = 0,cit[i] = 0;
    for(int i = 1; i <= m; ++i){
      scanf("%d%d%lld",&l,&r,&val);
      addb(l, val);addb(r+1, -val);
      addc(l, (l-1)*val);addc(r+1,-r*val);
    }
    scanf("%d",&q);
    int ans = n;
    while(q--){
      scanf("%lld%d",&val,&r);
      if(allsum(r, n)>=val)ans--;
    }
    printf("%d\n", ans);
  }
  return 0;
}

CODEVS1082: 改段求段模板 传送门

/*
s[n] = n*(d1+..+dn)-(c1+...+cn)
c[i] = (i-1)*d[i]
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;
const int N = 2e5 + 7;
const int INF = 0x3f3f3f3f;
LL d[N], c[N], ar[N];
int n, q;
void add(LL *a, int x, LL v){
  while(x <= n){
    a[x] += v;
    x += lowbit(x);
  }
}
LL query(LL *a, int x){
  LL sum = 0;
  while(x > 0){
    sum += a[x];
    x -= lowbit(x);
  }
  return sum;
}
int main(){
  while(~scanf("%d", &n)){
    for(int i = 1; i <= n; ++i){
      scanf("%lld", &ar[i]);
      add(d, i, ar[i]-ar[i-1]);
      add(c, i, (i-1)*(ar[i]-ar[i-1]));
    }
    scanf("%d", &q);
    while(q--){
      int op, l, r;
      LL x;
      scanf("%d", &op);
      if(op == 1){
        scanf("%d%d%lld", &l, &r, &x);
        add(d, l, x);add(d, r+1, -x);
        add(c, l, (l-1)*x);add(c, r+1, -1*r*x);
      }else{
        scanf("%d%d", &l, &r);
        LL sum1 = (l-1)*query(d, l-1)-query(c, l-1);
        LL sum2 = r*query(d, r)-query(c, r);
        printf("%lld\n", sum2 - sum1);
      }
    }
  }  
  return 0;
}

//sum[i] = sigma(ar[x])+(i+1)*sigma(delta[x])-sigma(x*delta[x])
#include <cstdio>
#include <algorithm>
#include <cstring>
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long LL;
const int N = 2e5 + 7;
const int INF = 0x3f3f3f3f;
LL delta[N], deltai[N], ar[N], pre[N];
int n, q;
void add(LL *a, int x, LL v){
  while(x <= n){
    a[x] += v;
    x += lowbit(x);
  }
}
LL query(LL *a, int x){
  LL sum = 0;
  while(x > 0){
    sum += a[x];
    x -= lowbit(x);
  }
  return sum;
}
int main(){
  while(~scanf("%d", &n)){
    pre[0] = 0;
    for(int i = 1; i <= n; ++i){
      scanf("%lld", &ar[i]);
      pre[i] = pre[i-1] + ar[i];
    }
    scanf("%d", &q);
    while(q--){
      int op, l, r;
      LL x;
      scanf("%d%d%d", &op,&l,&r);
      if(op == 1){
        scanf("%lld", &x);
        add(delta, l, x);add(delta, r+1, -x);
        add(deltai, l, l*x);add(deltai, r+1, -x*(r+1));
      }else{
        LL sum1 = pre[l-1]+l*query(delta, l-1)-query(deltai, l-1);
        LL sum2 = pre[r]+(r+1)*query(delta, r)-query(deltai, r);
        printf("%lld\n", sum2 - sum1);
      }
    }
  }  
  return 0;
}