FJUToj-1608-求平均数（树状数组）

求平均数

TimeLimit:1000MS MemoryLimit:128000KB

64-bit integer IO format:%lld

Problem Description

Input

多组测试数据
每组测试数据的第一行是两个数n,q
n表示有n个可重复容器（里面的元素可重复）编号是1~n。
q表示有q个操作 (1<=n，q<=100000)
操作：1 a b 在容器a中加入一个整数b (1<=a<=n,-10000<=b<=10000)
操作：2 l r 求集合l到集合r内的所有数的平均数 (1<=l<=r<=n)

Output

输出答案以最简分数表示。
如果是整数x则输输出如x/1的形式
如果答案是0则输出0/1
如果答案是负数则输出如-a/b的形式
如果查询时要求的平均数的数字个数是0个的话就输出Error!

SampleInput

SampleOutput

1/1
1/1
Error!
7/2
-1/1
0/1


这题可以说包含了树状数组的两个基本概念：一个是区间查询，一个是单点更新。
将输入的值保存在数组a，单点更新，c数组用于区间查询，查看范围的数的个数
这题用了两个树状数组，一个查询，一个用来计算，不然一个个查询必然T。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define N 100005
 4 using namespace std;
 5 int n,q,a[N],c[N];
 6 int lowbit(int x)
 7 {
 8     return x&(-x);
 9 }
10 void add1(int x,int y)
11 {
12     while(x<=n)
13     {
14         a[x]+=y;
15         x+=lowbit(x);
16     }
17 }
18 int sum1(int x)
19 {
20     int ans=0;
21     while(x>0)
22     {
23         ans+=a[x];
24         x-=lowbit(x);
25     }
26     return ans;
27 }
28 void add2(int x,int y)
29 {
30     while(x<=n)
31     {
32         c[x]+=y;
33         x+=lowbit(x);
34     }
35 }
36 int sum2(int x)
37 {
38     int ans=0;
39     while(x>0)
40     {
41         ans+=c[x];
42         x-=lowbit(x);
43     }
44     return ans;
45 }
46 int gcd(int m,int n)//求分子分母的最大公约数
47 {
48     int r;
49     while(n)
50     {
51         r=m%n;
52         m=n;
53         n=r;
54     }
55     return m;
56 }
57 int main(void)
58 {
59     int m,x,y;
60     while(~scanf("%d%d",&n,&q))
61     {
62         memset(a,0,sizeof(a));
63         memset(c,0,sizeof(c));
64         while(q--)
65         {
66             scanf("%d%d%d",&m,&x,&y);
67             if(m==1)
68             {
69                 add1(x,1);
70                 add2(x,y);
71             }
72             else
73             {
74                     int num1=sum2(y)-sum2(x-1);//计算这个范围里的和
75                     int num2=sum1(y)-sum1(x-1);//查看这个范围里有没有数
76                     if(num2==0)
77                         printf("Error!
");
78                     else if(num1==0)
79                         printf("0/1
");
80                     else if(num1<0)
81                     {
82                         printf("-");
83                         num1=-num1;
84                         int l=gcd(num1,num2);
85                         printf("%d/%d
",num1/l,num2/l);
86                     }
87                     else
88                     {
89                         int l=gcd(num1,num2);
90                         printf("%d/%d
",num1/l,num2/l);
91                     }
92 
93 
94             }
95         }
96     }
97 }

附上一张树状数组的图片，怕以后忘了这个概念。