首页 > 编程语言 > 详细

【树状数组】树状数组一维二维模板

时间:2015-03-15 23:02:23      阅读:313      评论:0      收藏:0      [点我收藏+]

以下模板都是点更新,区间查询,如果是区间更新点查询,只需将利用lowbit的循环方向倒过来


一维:

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

void add(int x, int val)
{
    for(int i = x; i <= n; i += lowbit(i)) C[i] += val;
}

int sum(int x)
{
    int ret = 0;
    for(int i = x; i > 0; i -= lowbit(i)) ret += C[i];
    return ret;
}

二维:

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

void add(int x, int y, int val)
{
    for(int i = x; i <= n; i+=lowbit(i)) {
        for(int j = y; j <= n; j+=lowbit(j)) {
            C[i][j] += val;
        }
    }
}

int sum(int x, int y)
{
    int ret = 0;
    for(int i = x; i > 0; i-=lowbit(i)) {
        for(int j = y; j > 0; j-=lowbit(j)) {
            ret += C[i][j];
        }
    }
    return ret;
}

【树状数组】树状数组一维二维模板

原文:http://blog.csdn.net/j_sure/article/details/44281411

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