A+B Problem 小题大做（1）

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

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

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

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

#include<cstdio>
int a[3],c[3],n=2;
int lowbit(int x){
    return x&-x;
}
void build(){ //O(n) 建树（初始化）
    for(int i=1;i<=n;i++){
        c[i]+=a[i];
        if(i+lowbit(i)<=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("%d%d",&a[1],&a[2]);
    build();
    printf("%d\n",query(2));
    return 0;
}

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

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

PS：站长已修改此博文

Update On 20210314: 修复了出锅的代码，现在的符号显示正常了！[aru_1]