数据结构--zkw线段树

本文主要是介绍数据结构--zkw线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

好几天没写了，写点儿奇怪的东西，一个不好理解的黑科技。

---

zkw线段树，顾名思义，就是zkw大神发明的线段树。
由于我实在是太弱了，无法讲述zkw大神的高深的ppt，就留一个下载网址：统计的力量（zkw线段树）
我这里要说的，就是zkw线段树的具体用法，首先，原版zkw只能做到单点修改&区间查询，可是这并无卵用，因为树状数组完全可以替代它。
但是，zkw经过一些数学变化，就可以区间修改&区间查询，而且常数极小，比普通线段树小得多。
利用差分，我们可以将区间修改变为$O(1)$的时间。
首先，我们称原数组为$A$，得到原数组的差分数组后称之为$T$，然后将差分数组做前缀和得到数组$S$，就可以得到原数组的值。

$$S_i=T_1+T_2+...+T_i=(A_1-0)+(A_2-A_1)+...+(A_i-A_{i-1})=A_i$$
所以，从1到k的原数值和就可以这样得出：

$$\sum_{i=1}^k A_i=\sum_{i=1}^k S_i=\sum_{i=1}^k {(k-i+1)*T_i}=(k+1)*S_k-\sum_{i=1}^k {i*T_i}$$
这样我们只需要维护 $T_i$的前缀和，以及 $i*T_i$的前缀和就可以了。
我们记 $i*T_i$的前缀和为 $F_i$，那么最后的区间和公式就是这样的：
$$\sum_{i=x}^{y} A_i=\big((y+1)*S_y-F_y\big)-\big(x*S_{x-1}-F_{x-1}\big)$$
这样就是 $O(logn)$区间查询，还有，因为修改之后还要调整，所以区间修改也变成 $O(logn)$的时间了。
附上我丑陋的代码：
code：

#include<bits/stdc++.h>
using 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的思想去写一棵真正的线段树，效率较高，实用；虽然我还没写（手动滑稽）

这篇关于数据结构--zkw线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---