东北四省赛2019 H

四省赛2019 H"/>

东北四省赛2019 H

看了下题解思路才做出来的，一开始根本没有思路，还以为是线段树维护。
要掌握分析题目的方法：先在样例上尝试，各种方法，并且结合题目，看上去不是线段树就是树状数组，并且也不是简单的维护前缀和，并且有区间修改的操作，想到维护差分数组的树状数组。
最后要思路清晰得得出结论，便可找到合适的算法或数据结构解决，此题结论便是：构造差分数组，维护两个树状数组，一个是普通差分数组，另外一个是只维护大于0值的差分数组。

在这里总结一下个人对树状数组与线段树区别的理解：

树状数组（1）复杂度稳定O(logn)，常数小，比线段树快，（2）且不用开四倍空间，（3）而且个人感觉树状数组好写（线段树懒标记难写，wtcl）。
而线段树的优点便是能够进行很多神奇操作，比树状数组的用途广。

总结下树状数组的两种基本用法：

1.直接维护数组，可进行的操作有区间查询和单点修改。并且线段树的查询区间是前缀和。
2.维护差分数组。由于差分数组的特点，对原数组的区间修改，在差分数组中只需要修改两个点即 左端点和右端点的右一位。所以相当于能对原数组进行区间修改 和单点（原数组）查询（就是差分数组前缀和）了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) ((x)&(-x))
const int N = 1e5+10;
ll tree[N],a[N],n,m,b[N],tree2[N];
void update(int x,int k)
{while(x<=n){tree[x]+=k;x+=lowbit(x);}
}
void update2(int x,int k)
{while(x<=n){tree2[x]+=k;x+=lowbit(x);}
}
ll query(int x)
{ll sum=0;while(x){sum+=tree[x];x-=lowbit(x);}return sum;
}
ll query2(int x)
{ll sum=0;while(x){sum+=tree2[x];x-=lowbit(x);}return sum;
}
int main()
{int t;cin>>t;while(t--){memset(tree,0,sizeof(tree));memset(tree2,0,sizeof(tree2));scanf("%lld %lld",&n,&m);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);b[i]=a[i]-a[i-1];if(b[i]>0)update(i,b[i]);update2(i,b[i]);}while(m--){int flag,l,r,k;scanf("%d",&flag);if(flag==1){scanf("%d %d %d",&l,&r,&k);update2(l,k);update2(r+1,-k);b[l]+=k;if(b[l]>=k){update(l,k);}else if(b[l]>0){update(l,b[l]);}if(b[r+1]>=k){update(r+1,-k);}else if(b[r+1]>0){update(r+1,-b[r+1]);}b[r+1]-=k;}else{scanf("%d %d",&l,&r);printf("%lld\n",query2(l)+query(r)-query(l));}}}return 0;
}