首页 > 编程语言 > 详细

(模板) 树状数组

时间:2019-10-31 21:32:29      阅读:73      评论:0      收藏:0      [点我收藏+]

—————————————————————————————————————————————————— —————————————————————前排护眼——————————————————————— ——————————————————————————————————————————————————

ll data[500003];        //存单点数据
ll sub[500003];        //data的差分数组
ll tree[500003];        //tree[i]表示date[i-lowbit(i)+1]+...+data[i]

 

//表示x的二进制表示从右向左第一个1换成十进制为多少

inline int lowbit(int x){       
    return x&(-x);
}

单点修改,区间查询

//建树

void build(){      
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j+=lowbit(j)){
            tree[j]+=data[i];
        }
    }
}   

 

//单点更新

void add(int x,int d){      
    while(x<=n){
        tree[x]+=d;
        x+=lowbit(x);    
    }
}

 

//区间查询

inline int range_query(int l,int r){    
    int ans1=0,ans2=0;
    for(int i=r;i>0;i-=lowbit(i)){
        ans1+=tree[i];
    }
    for(int i=l-1;i>0;i-=lowbit(i)){
        ans2+=tree[i];
    }
    return ans1-ans2;
}

区间修改,单点查询

//用差分数组建树

void build(){      
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j+=lowbit(j)){
            tree[j]+=sub[i];
        }
    }
}   

 

//区间修改

void range_add(int l,int r,int d){      
    for(int i=l;i<=n;i+=lowbit(i)){
        tree[i]+=d;
    }
    for(int i=r+1;i<=n;i+=lowbit(i)){
        tree[i]-=d;
    }
}

 

//单点查询

inline int query(int x){
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i)){
        ans+=tree[i];
    }
    return ans;
}

 

(模板) 树状数组

原文:https://www.cnblogs.com/xiaozezz/p/11773699.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!