好几天没写了，写点儿奇怪的东西，一个不好理解的黑科技。
zkw线段树，顾名思义，就是zkw大神发明的线段树。
由于我实在是太弱了，无法讲述zkw大神的高深的ppt，就留一个下载网址： 我这里要说的，就是zkw线段树的具体用法，首先，原版zkw只能做到单点修改&区间查询，可是这并无卵用，因为树状数组完全可以替代它。 但是，zkw经过一些数学变化，就可以区间修改&区间查询，而且常数极小，比普通线段树小得多。 利用差分，我们可以将区间修改变为O(1)的时间。 首先，我们称原数组为A，得到原数组的差分数组后称之为T，然后将差分数组做前缀和得到数组S，就可以得到原数组的值。 Si=T1+T2+...+Ti=(A1−0)+(A2−A1)+...+(Ai−Ai−1)=Ai
所以，从1到k的原数值和就可以这样得出： ∑i=1kAi=∑i=1kSi=∑i=1k(k−i+1)∗Ti=(k+1)∗Sk−∑i=1ki∗Ti
这样我们只需要维护 Ti的前缀和，以及 i∗Ti的前缀和就可以了。 我们记 i∗Ti的前缀和为 Fi，那么最后的区间和公式就是这样的： ∑i=xyAi=((y+1)∗Sy−Fy)−(x∗Sx−1−Fx−1)
这样就是 O(logn)区间查询，还有，因为修改之后还要调整，所以区间修改也变成 O(logn)的时间了。 附上我丑陋的代码： code： #includeusing namespace std;int n,m,M;long long T[410000];long long f[410000];long long ff[410000];long long queryf(int s,int t){ long long ans=0; for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1){ if(~s&1)ans+=f[s^1]; if(t&1)ans+=f[t^1]; } return ans;}long long queryff(int s,int t){ long long ans=0; for(s=s+M-1,t=t+M+1;s^t^1;s>>=1,t>>=1){ if(~s&1)ans+=ff[s^1]; if(t&1)ans+=ff[t^1]; } return ans;}void add(int s,long long v){ f[s+M]+=v; ff[s+M]=s*(f[s+M]); s+=M; for(s>>=1;s;s>>=1){ f[s]=f[s<<1]+f[s<<1|1]; ff[s]=ff[s<<1]+ff[s<<1|1]; }}int main(){ scanf("%d %d",&n,&m); for(M=1;M<=n+1;M<<=1); for(int i=1;i<=n;i++){ scanf("%lld",&T[i+M]); } for(int i=M+1;i<=M+n;i++){ f[i]=T[i]-T[i-1]; ff[i]=(i-M)*f[i]; } for(int i=M-1;i>=1;i--){ f[i]=f[i<<1]+f[i<<1|1]; ff[i]=ff[i<<1]+ff[i<<1|1]; } for(int i=1;i<=m;i++){ int tmp; scanf("%d",&tmp); if(tmp&1){ int x,y; long long k; scanf("%d %d %lld",&x,&y,&k); add(x,k); add(y+1,-k); } else{ int x,y; scanf("%d %d",&x,&y); printf("%lld\n",(y+1)*queryf(1,y)-queryff(1,y)-(x)*queryf(1,x-1)+queryff(1,x-1)); } } return 0;}
贴一下时间效率区别：
这是普通线段树：
这是zkw线段树： 
差距竟然如此之大，常数小就是不一样啊。。 之后就是废话了，这个zkw还是非常不实用的，我不建议大家用，最好是用zkw的思想去写一棵真正的线段树，效率较高，实用；虽然我还没写（手动滑稽）