首页 > 代码库 > 线段树的基础非递归的使用
线段树的基础非递归的使用
以下为基础模板
//原数组下标+1=线段树下标
//线段树下标+N-1=存储下标 (空出前和尾的一个位置)
//原数组下标+N=存储下标
#define maxn 100007
int A[maxn],Sum[maxn<<2],add[maxn<<2];
int N;//N为扩充元素的个数
int n;//n为原数组元素的个数
void Build(int n)
{
N=1;
while(N<n+2)
N<<=1;//相同于N=N*2;
for(int i=1;i<=n;i++)
Sum[i+N]=A[i];
for(int i=N-1;i>=1;i--)
{
Sum[i]=Sum[i<<1]+Sum[i<<1|1];
add[i]=0;//清空非叶的add标记
}
}
void Update(int L,int C)
{
for(int i=N+L;i!=0;i>>=1)
Sum[i]+=C;
}
int Query(int L.int R)
{
int ans=0;
for(int s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1)
//s和t代表之前左右蓝色节点,s^t^1在s和t的父亲相同时值为0
{
if(~s&1)//判断奇偶性的代码 偶数返回1
ans+=Sum[s^1];//若s为6则s^1为7,是左右子树的相互运算等同于s+1
if( t&1)
ans+=Sum[t^1];//等同于t-1;
}
return ans;
}
void Update_interval(int L,int R,int C)
{
int s,t,Ln=0,Rn=0,x=1;
//Ln: s一路走来已经包含了几个数
//Rn: t一路走来已经包含了几个数
//x: 本层每个节点包含几个数
for(s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1,x<<=1)
{
//更新Sum
Sum[s]+=C*Ln;
Sum[t]+=C*Rn;
if(~s&1)
add[s^1]+=C,Sum[s^1]+=C*x,Ln+=x;
if( t&1)
add[t^1]+=C,Sum[t^1]+=C*x,Rn+=x;
}
//相同之后继续更新上层的Sum;
if(;s;s>>=1,t>>=1)
{
Sum[s]+=C*Ln;
Sum[t]+=C*Rn;
}
}
int Query_interval(int L,int R)
{
int s,t,Ln=0,Rn=0,x=1;
int ans=0;
for(s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1,x<<=1)
{
//根据标记更新
if(add[s]) ans+=add[s]*Ln;
if(add[t]) ans+=add[t]*Rn;
if(~s&1) ans+=Sum[s^1],Ln+=x;
if( t&1) ans+=Sum[t^1],Rn+=x;
}
for(;s;s>>=1,t>>=1)
{
ans+=add[s]*Ln;
ans+=add[t]*Rn;
}
return ans;
}
参考链接 http://blog.csdn.net/zearot/article/details/48299459
线段树的基础非递归的使用
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。