HDU1166 敌兵布阵 BZOJ1012 最大数[树状数组]

一、前置知识-树状数组

树状数组(binary indexed tree)是一种简洁的代码量很小的数据结构，能够高效的处理前缀区间上的问题。在很多情况下能写树状数组解决的就不用码半天线段树了。

树状数组支持两种操作：

a)单点更新：例如更改序列中的某一个元素的值，复杂度O(logn)

b)前缀查询：查询序列中的前缀信息，例如，区间[1,n]中的最大值或者区间和，复杂度O(logn)

同时由于求和操作的“可减性”，可以通过查询两次前缀和实现求解序列的区间和

二、HDU1166 树状数组求解区间和

题意：单点修改元素，查询区间和，树状数组求区间和实现。

代码：

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 const int maxn = 5e4+5;
 6 int N,A[maxn],C[maxn];
 7 inline int lowbit(int x)
 8 {
 9     return x&(-x); 
10 }
11 void Update(int index,int val)
12 {
13     while(index<=N)
14     {
15         C[index] += val;
16         index += lowbit(index);
17     }
18 }
19 int Query_Sum(int index)
20 {
21     int res = 0;
22     while(index)
23     {
24         res += C[index];
25         index -= lowbit(index);
26     }
27     return res;
28 }
29 void Init()
30 {
31     scanf("%d",&N);
32     memset(C,0,sizeof(C));
33     memset(A,0,sizeof(A));
34     for(int i=1;i<=N;i++)
35     {
36         scanf("%d",&A[i]);
37         Update(i,A[i]);
38     }
39 }
40 void Solve(int t)
41 {
42     printf("Case %d:
",t);
43     int a,b;
44     char ins[10];
45     while(scanf("%s",ins)!=EOF)
46     {
47         if(ins[0]=='E')
48             break;
49         scanf("%d%d",&a,&b);
50         if(ins[0]=='Q')
51             printf("%d
",Query_Sum(b)-Query_Sum(a-1));
52         if(ins[0]=='A')
53             Update(a,b);
54         if(ins[0]=='S') 
55             Update(a,-b);
56     }
57 }
58 int main()
59 {
60     int T;
61     scanf("%d",&T);
62     for(int t=1;t<=T;t++)
63     {
64         Init();
65         Solve(t);    
66     }    
67     return 0;
68 }

View Code

三、BZOJ1012 树状数组求解前缀最大值

题意：在空队列里不断向队尾插入元素，过程中查询倒数第K大的元素，树状数组求最值实现。

代码：

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 const int maxn = 2e5+10;
 6 int M,cnt;
 7 long long D,val,ans,A[maxn],C[maxn];
 8 char S[5];
 9 inline long long lowbit(long long x) {return x&(-x);}
10 void update(int index,long long value)
11 {
12     while(index)
13     {
14         C[index] = max(C[index],value);
15         index -= lowbit(index);
16     }
17 }
18 long long query(int index)
19 {
20     long long res = 0;
21     while(index<=M)
22     {
23         res = max(res,C[index]);
24         index += lowbit(index);
25     }
26     return res;
27 }
28 void Init()
29 {
30     cnt = 0;
31     ans = 0;
32     memset(C,0,sizeof(C));
33 }
34 void Solve()
35 {
36     for(int i=0;i<M;i++)
37     {
38         scanf("%s%lld",S,&val);
39         if(S[0]=='A')
40         {
41             cnt++;
42             update(cnt,(val+ans)%D);
43         }
44         else
45         {
46             ans = query(cnt-val+1);
47             printf("%lld
",ans);
48         }
49     }
50 }
51 int main()
52 {
53     while(scanf("%d%lld",&M,&D)!=EOF)
54     {
55         Init();
56         Solve();
57     }
58     return 0;
59 }

View Code