欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

树状数组和线段树的总结

程序员文章站 2023-04-08 09:56:20
先说树状数组吧 主要有lowbit,update,getsum lowbit的作用就是找到该节点的父节点或子节点 图 (https://www.cnblogs.com/George1994/p/7710886.html) 注意了 a数组存的是原来的数 c数组的意义代表着c[i] 就是前i项的和 线段 ......

先说树状数组吧  主要有lowbit,update,getsum

int lowbit(int x)
{
    return x&(-x);
}
int update(int x,int date)
{
    while(x<=y)
    {
        c[x]+=date;
        x+=lowbit(x);
    }
}
int getsum(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}

lowbit的作用就是找到该节点的父节点或子节点   图 (https://www.cnblogs.com/George1994/p/7710886.html)

树状数组和线段树的总结

注意了  a数组存的是原来的数  c数组的意义代表着c[i] 就是前i项的和

 

线段树的话

树状数组和线段树的总结

差不多两个数组搞定一个tree【n】和一个add【n】

先是建立树

线段树是从1这个节点开始的

void build(int l,int r,int k)//l,r为建树的范围 
{
    if(l==r)
    {
        cin>>tree[k];
        return ;
    }
    int m=(l+r)>>1;
    build(l,m,k<<1);//递归建立数 
    build(m+1,r,k<<1|1);
    tree[k]=tree[k<<1]+tree[k<<1|1];//求和 
}

 

自我觉得这个是比较灵活的,对这个改动一下就成为不同的功能,比如最大值

void build(int l,int r,int k)
{
    if(l==r)
    {
        cin>>tree[k];
        return ;
    }
    int m=(l+r)>>1;
    build(l,m,k<<1);
    build(m+1,r,k<<1|1);
    //tree[k]=tree[k<<1]+tree[k<<1|1];
    tree[k]=max(tree[k<<1],tree[k<<1|1]); 
}

这样就变成了父节点 为子节点的最大值

 

然后是点更新

void update(int ee,int c,int l,int r,int k)
{
    if(l==r)
    {
        tree[k]+=c;
        //tree[k]=c;  这样就是更改这个数,而不是加 
        return ;
    }
    int m=(l+r)>>1;
    if(ee<=m) update(ee,c,l,m,k<<1);//ee为需要更新的叶子节点,通过递归找 
    else update(ee,c,m+1,r,k<<1|1);
    tree[k]=tree[k<<1]+tree[k<<1|1];
}

 

然后是区间更新  ,这里需要懒标记,这个确实比较难理解

void update(int x,int y,int c,int l,int r,int k)//x,y为需要更新区间,l,r为k这一节点的管理范围 
{
    if(x<=l&&y>=r)
    {
        tree[k]=c*(r-l+1);//这一点为c乘以这一点管理的数量
        add[k]=c;//把这一点标记一下,为懒标记
        return;//注意是结束了 
    }
    int m=(l+r)>>1;
    pushdown(k,m-l+1,r-m);//下推标记
    if(x<=m) update(x,y,c,l,m,k<<1);
    if(y>m) update(x,y,c,m+1,r,k<<1|1);//注意 这里不是else 而是都要更新并查找 
    tree[k]=tree[k<<1]+tree[k<<1|1]; 
} 
void pushdown(int k,int ln,int rn)//ln,rn为左子树,右子树的数字数量。 
{
    if(add[k])
    {
        add[k<<1]+=add[k];
        add[k<<1|1]+=add[k];//传递这个标记
        
        sum[k<<1]+=add[k]*ln;
        sum[k<<1|1]+=add[k]*rn;
        add[k]=0;
    }
} 

上面是要求和的下推标记,但如果说是这道题

为这个区间都改变成一样的数,而不是相加一样的数

void pushdown(int k,int ln,int rn){
    if(add[k]){
        add[k<<1]=add[k];
        add[k<<1|1]=add[k];
sum[k<<1]=add[k]*ln; sum[k<<1|1]=add[k]*rn; add[k]=0; } }

 

最后是区间求和

int query(int x,int y,int l,int r,int k)
{
    if(x<=l&&r<=y)
    {
        return tree[k];
    }
    int m=(l+r)>>1;
    pushdown(k,m+1-l,r-m);
    
    int ans=0;
    if(x<=m) ans+=query(x,y,l,m,k<<1);
    if(y>m) ans+=query(x,y,m+1,r,k<<1|1);
    return ans;
}