树状数组

树状数组，最关键的就是关于二进制位末尾为零的函数——lowbit()的应用。

关于lowbit()，可以用宏定义。

#define lowbit(x) x&-x;

开始构造树状数组。设树状数组为C[ ],求和数组为A[ ]。

C1=A1
C2=A1+A2
C3=A3
C4=A1+A2+A3+A4
C5=A5
C6=A5+A6
C7=C7
C8=A1+A2+.....+A8

树状数组巧妙的利用二分，使得求出A[ ]的区间和加快。

上题目：

链接：https://www.nowcoder.com/acm/contest/77/B
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

给一个数列，会有多次询问，对于每一次询问，会有两种操作：

1：给定两个整数x, y, 然后在原数组的第x位置上加y；

2：给定两个整数l，r，然后输出数组从第l位加到第r位数字的和并换行

输入描述:

第一行有两个整数n, m（1 <= n, m <= 100000）代表数列的长度和询问的次数
第二行n个数字，对于第i个数字a[i]，(0<=a[i]<=100000)。
接下来m行，每一行有三个整数f, x, y。第一个整数f是1或者是2，代表操作类型，如果是1，接下来两个数x,y代表第x的位置上加y，如果是2，则求x到y的和，保证数据合法。

输出描述:

输出每次求和的结果并换行

示例1

输入

10 2
1 2 3 4 5 6 7 8 9 10
1 1 9
2 1 10

输出

 1 #include<stdio.h>
 2 #define lowbit(x) x&(-x);///宏定义的lowbit
 3 int c[100006],a[100006];
 4 
 5 void change(int ti,int fi,int n)
 6 {
 7     while(ti<=n){
 8         c[ti]+=fi;
 9         ti+=lowbit(ti);
10     }
11 }
12 
13 int sum(int num)
14 {
15     int ans=0;
16     while(num){ ///1-num区间的求和
17         ans+=c[num];
18         num-=lowbit(num);
19     }
20     return ans;
21 }
22 
23 int ask(int ti,int fi)///求出区间和
24 {
25     return sum(fi)-sum(ti-1);
26 }
27 
28 int main()
29 {
30     int n,m;
31     while( ~scanf("%d%d",&n,&m)){
32         for(int i=1;i<=n;i++){
33             scanf("%d",&a[i]);
34             change(i,a[i],n); ///一边录入a[]，一边构造树
35         }
36         int ord,ti,fi;
37         for(int i=1;i<=m;i++){
38             scanf("%d%d%d",&ord,&ti,&fi);
39             if(ord==1){
40                 change(ti,fi,n);
41             }
42             else
43                 printf("%d
",ask(ti,fi));
44         }
45     }
46     return 0;
47 }

View Code

该题简单操作树状数组，利用特性降低时间复杂度。