A+B Problem 小题大做(1)

vgakbzc 11 0

众多周知,很多人在开始学习一门编程语言的时候都要做掉这道题,也就是输入 a,b 两个整数 (|a|,|b| <= 1e9) ,输出两数之和。那么这道题目很显然是一个区间求和的问题,可以很“方便”地用树状数组解决。

树状数组是一个通常被用于维护单点修改,区间查询的简单数据结构(但是也可以用一些奇技淫巧维护区间修改区间查询等,尽管这题里面我们似乎不用修改)。[aru_11]

这个数据结构具体是什么样的,可以问问度娘,这里就不讲了。

下面贴上代码,可阅读注释。

#include
int a[3],c[3],n=2;
int lowbit(int x){
    return x&amp;-x;
}
void build(){ //O(n) 建树(初始化)
    for(int i=1;i&lt;=n;i++){
        c[i]+=a[i];
        if(i+lowbit(i)&lt;=n)
            c[i+lowbit(i)]+=a[i];
    }
}
// 最常见的建树方法是对于每一个节点都 update 一下,但是太慢了,复杂度 O(n log n) 
int query(int x){ //a+b 的结果在 int 范围内,不用考虑溢出 AwA
    int res=0;
    while(x){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
//没有修改,不写 update 了 QAQ
int main() {
    scanf(&quot;%d%d&quot;,&amp;a[1],&amp;a[2]);
    build();
    printf(&quot;%d\n&quot;,query(2));
    return 0;
}

关于树状数组,以后可能会出一篇文章讲,由于现在已经 11 点了,所以作者就咕咕咕了……

所以,这道题的树状数组做法其实真的很简单,不是吗?[aru_14]

PS:站长已修改此博文

发表评论 取消回复
表情 图片 链接 代码

分享