A+B Problem 小题大做(1)

vgakbzc 147 5

众多周知,很多人在开始学习一门编程语言的时候都要做掉这道题,也就是输入 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]

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

  1. 光阴似箭
    光阴似箭 Lv 3

    希望做到周更[aru_1]

    • vgakbzc
      vgakbzc Lv 1

      @光阴似箭天哪,周更可难了啊……[aru_15]
      作者会尽量月更周更的[aru_1]
      谢谢支持AwA

    • 杨承翰
      杨承翰 站长

      @vgakbzc你为什么不登陆作者再回复评论?

  2. 贺飞
    贺飞 Lv 1

    喂喂喂,代码出锅了

    • vgakbzc
      vgakbzc Lv 1

      @贺飞已经修复了[aru_3]

分享