我是靠谱客的博主 高兴钻石,这篇文章主要介绍HDUOJ_1166_敌兵布阵_线段树,现在分享给大家,希望可以做个参考。

本题是一道基本的线段树裸题,是求区间和的问题。

我用了堆式线段树写这道题,还是比较容易理解的,要掌握线段树的应用,就要熟悉递归调用,总之就是不断地递归向子区间,直到进入完全覆盖的区间然后统计区间和即可。只要理解了递归这一核心思想就基本明白了简单线段树如何操作。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=50001; const int inf=0x7f7f7f7f; struct SegmentTree//堆式线段树 { int l,r,sum; }tree[N*4]; void BuildTree(int l,int r,int idx) { tree[idx].l=l; tree[idx].r=r; tree[idx].sum=0; if (l==r) return; int mid=(l+r)>>1; BuildTree(l,mid,idx<<1);//左移一位是乘二 BuildTree(mid+1,r,idx<<1|1);//乘二加一 } void Insert (int i,int j,int idx) { if (tree[idx].l==tree[idx].r) { tree[idx].sum+=j; return; } int mid=(tree[idx].l+tree[idx].r)>>1; if (i<=mid) Insert (i,j,idx<<1); else Insert (i,j,idx<<1|1); tree[idx].sum=tree[idx<<1].sum+tree[idx<<1|1].sum; } int Query (int l,int r, int idx) { if (tree[idx].l==l&&tree[idx].r==r) return tree[idx].sum; int mid=(tree[idx].l+tree[idx].r)>>1; if (r<=mid) return Query(l,r,idx<<1); else if (l>mid) return Query(l,r,idx<<1|1); return Query(l,mid,idx<<1)+Query(mid+1,r,idx<<1|1); } int main() { int ca,T=0; for (scanf ("%d",&ca);ca--;) { cout<<"Case "<<++T<<":n";//注意Case 后面有个空格 int n; scanf ("%d",&n); BuildTree(1,n,1);//先建立一棵空树 for (int i=1;i<=n;i++) { int x; scanf ("%d",&x); Insert(i,x,1); } char s[11]; while (scanf ("%s",s),s[0]!='E') { int i,j; scanf ("%d%d",&i,&j); if (s[0]=='A') Insert (i,j,1); else if (s[0]=='S') Insert(i,-j,1); else printf ("%dn",Query(i,j,1)); } } return 0; }

最后

以上就是高兴钻石最近收集整理的关于HDUOJ_1166_敌兵布阵_线段树的全部内容,更多相关HDUOJ_1166_敌兵布阵_线段树内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(97)

评论列表共有 0 条评论

立即
投稿
返回
顶部