本文主要是介绍zkw线段树模板及理解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
zkw线段树模板及理解
线段树作为很重要的一个知识点一直却没有学会，今天突然接触到了一种新的线段树写法，相比原来的较简单，叫zkw线段树。
这个线段树并不需要递归的来写，并且在单点查询上有很好的效果。
zkw需要建立一个满二叉树来实现。
首先是一个区间求和的建树的操作：
void build(int x)
{for(M=1;M<=n+1;M<<1);for(int i=M+1;i<=n+M;i++)scanf("%d",&T[i]);for(int i=M-1;i;i--)T[i]=T[i<<1]+T[i<<1|1];
}void updata(int x,int val)
{T[x+=M]+=val;for(x>>=1;x>=1;x>>=1){T[x]=T[x<<1]+T[x<<1|1];}
}ll query(int l,int r)
{l=l+M-1,r=r+M+1;ll ans=0;for(;l^r^1;l>>=1,r>>=1){if(~l&1)ans+=T[l^1];if(r&1) ans+=T[r^1];}return ans;
}#include <cstdio>
#include <iostream>
#include<cstring>
typedef long long ll;
using namespace std;
#define maxn 200001
ll T[maxn*4];
int M,n;
void build()
{for(M=1;M<=n+1;M<<=1);for(int i=M+1;i<=n+M;i++)scanf("%d",&T[i]);for(int i=M-1;i;i--)T[i]=T[i<<1]+T[i<<1|1];
}void updata(int x,int val)
{T[x+=M]+=val;for(x>>=1;x>=1;x>>=1){T[x]=T[x<<1]+T[x<<1|1];}
}ll query(int l,int r)
{l=l+M-1,r=r+M+1;ll ans=0;for(;l^r^1;l>>=1,r>>=1){if(~l&1)ans+=T[l^1];if(r&1) ans+=T[r^1];}return ans;
}int main()
{int cas=0;int t;cin>>t;string s;for(int cas=1;cas<=t;cas++){memset(T,0,sizeof(T));printf("Case %d:\n",cas);cin>>n;build();while(cin>>s){if(s[0]=='E')break;int a,b;scanf("%d%d",&a,&b);if(s[0]=='A')updata(a,b);else if(s[0]=='S')updata(a,-b);elseprintf("%lld\n",query(a,b));}}
}
这篇关于zkw线段树模板及理解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
