这题目很有意思，让我学会了树状数组的差分，更加深刻理解了树状数组
树状数组的差分写法
1 void add(int x,int k) 2 { 3 for (int i = 1;i <= n;i += lowbit(i)) c[i] += k; 4 } 5 6 int sum(int x) 7 { 8 int ans = 0; 9 for (int i = x;i > 0;i -= lowbit(i)) ans += c[i]; 10 return ans; 11 } 12 13 { 14 add(l,x); 15 add(r+1,-x); 16 int zhi=sum(l)//就是a[l]的数值，前缀和。 17 }
题意：
很简单，输入n m
给n个a[i]，代表每栋楼要造的高度
接下来m个操作
输入op
当op等于1的时候输入l,r,val
区间l，r之间增加val高度
当op等于2的时候输入l，r
求区间l，r，最小的工作时长（这个我语文不好，举例吧 1 3 2需要3个工作时长 1 3 2 5需要6个工作时长，1 3 2 5 -> 0 2 1 4 -> 0 1 0 3 -> 0 0 0 3 -> 0 0 0 2 -> 0 0 0 1 -> 0 0 0 0）
思路：
差分树状数组
a[i]原本的高度 b[i]=a[i]-a[i-1]（前缀和） c[i]=b[i]>0?b[i]:0（后者比前者小，需要多出的工作时长）
所以答案就是 a[l]+(c[i]求和（l<i<r）)
增加的val高度，a[l]用一个前缀和树状数组 add（val，l）add（-val，r+1）
维护c[i]的树状数组特殊判断（tql这里的思考判断，做题的时候就是这里没处理好，于是代码写不出来）
其实就是把每个建筑的递增高峰写出来，如果前者比后者大，后者那个位置就是0
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<queue> 6 #include<stack> 7 #include<algorithm> 8 #include<stdio.h> 9 #include<map> 10 #include<set> 11 #define ll long long 12 #define lowbit(x) x&-x 13 using namespace std; 14 const int maxn=1e5+10; 15 int n,m,a[maxn],b[maxn]; 16 ll cnt[maxn],cn[maxn]; 17 void add1(int zhi,int x){ 18 for(int i=x;i<=n;i+=lowbit(i)){ 19 cn[i]+=(ll)zhi; 20 } 21 } 22 void add2(int zhi,int x){ 23 for(int i=x;i<=n;i+=lowbit(i)){ 24 cnt[i]+=(ll)zhi; 25 } 26 } 27 ll geshu1(int x){ 28 if(x==0){return 0;} 29 ll sum=0; 30 for(int i=x;i>0;i-=lowbit(i)){ 31 sum+=cn[i]; 32 } 33 return sum; 34 } 35 ll geshu2(int x){ 36 if(x==0){return 0;} 37 ll sum=0; 38 for(int i=x;i>0;i-=lowbit(i)){ 39 sum+=cnt[i]; 40 } 41 return sum; 42 } 43 int main() 44 { 45 int t; 46 scanf("%d",&t); 47 while(t--){ 48 scanf("%d%d",&n,&m); 49 for(int i=0;i<=n;i++){ 50 cnt[i]=0,cn[i]=0; 51 } 52 for(int i=1;i<=n;i++){ 53 scanf("%d",&a[i]); 54 b[i]=a[i]-a[i-1];int tt=(b[i]>0?b[i]:0); 55 add1(b[i],i); 56 add2(tt,i); 57 } 58 for(int i=1;i<=m;i++){ 59 int op; 60 scanf("%d",&op); 61 if(op==1){ 62 int l,r,val; 63 scanf("%d%d%d",&l,&r,&val); 64 add1(val,l);add1(-val,r+1);//差分 65 if(b[l]<0){ 66 int tt=-b[l]; 67 if(tt<val){ 68 add2(val-tt,l); 69 } 70 } 71 else{ 72 add2(val,l); 73 } 74 b[l]+=val; 75 if(b[r+1]>=0){ 76 int tt=min(b[r+1],val); 77 add2(-tt,r+1); 78 } 79 b[r+1]-=val; 80 } 81 else{ 82 int l,r; 83 scanf("%d%d",&l,&r); 84 printf("%lld\n",geshu2(r)-geshu2(l)+geshu1(l)); 85 } 86 } 87 } 88 return 0; 89 }
看了扩展
区间修改，单点输出
单点修改，区间输出
到区间修改和输出
tql（看了Top_Spirit博客）
数组cnt[n] 用来维护a[i]
a[1]+a[2]+...+a[n]= (c[1]) + (c[1]+c[2]) + ... + (c[1]+c[2]+...+c[n])
= n*c[1] + (n-1)*c[2] +... +c[n]
= n * (c[1]+c[2]+...+c[n]) - (0*c[1]+1*c[2]+...+(n-1)*c[n])
再维护一个数组cnt2[n]，cnt2[i] = (i-1)*c[i]
a[1]+a[2]+...+a[n]=n*geshu1(cnt,n) - geshu2(cnt2,n)
1 add1( l , val); 2 add1(r + 1, -val); 3 add2( l , (l - 1) * val); 4 add2 (r + 1, r* (-z));
原文：https://www.cnblogs.com/luoyugongxi/p/12191649.html
