HDU1754 && HDU1166 線段樹模板題

HDU1754

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1754

題目分析：對于給出的一個很長的區間，對其進行單點更新值和區間求最大值的操作，由于查詢的區間很大，且查詢次數多，這里用線段樹求解將是十分合適的

注意點：1.對于存放線段樹的陣列大小需要開大一些

　　　　2.對于c語言的字符輸入%c之前需要加一個空格保證輸入準確

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 
 5 const int N = 200005;
 6 int grade[N];
 7 int tree[N<<2];                    //這里建立的樹的陣列大小需要是N的4倍 否則不夠用 
 8 int n, m;
 9 
10 int max(int a, int b){
11     if(a > b) return a;
12     else return b;
13 }
14 
15 void build_tree(int start, int end, int node){                    //線段樹的建立 
16     if(start == end){
17         tree[node] = grade[start];
18     }else{
19         int mid = (start + end) / 2;
20         int left_node = node*2;
21         int right_node = node*2+1;
22         
23         build_tree(start, mid, left_node);
24         build_tree(mid+1, end, right_node);
25         tree[node] = max(tree[left_node], tree[right_node]);
26     }
27 }
28 
29 void update_tree(int start, int end, int node, int index, int value){    //單點更新值 
30     if(start == end){
31         tree[node] = value;
32     }else{
33         int mid = (start + end) / 2;
34         int left_node = node*2;
35         int right_node = node*2+1;
36         
37         if(index <= mid)
38             update_tree(start, mid, left_node, index, value);
39         else
40             update_tree(mid+1, end, right_node, index, value);
41         tree[node] = max(tree[left_node], tree[right_node]);
42     }
43 }
44 
45 int search_tree(int start, int end, int node, int l, int r){        //區間查詢最大值 
46     if(l > end || r < start){
47         return 0;
48     }else if(l <= start && r >= end){
49         return tree[node];
50     }else if(start == end){　　　　　　//這里的個遞回出口放在后面是有原因的，有可能存在start==end 但是l和r根本和start end沒有交集的情況，所以先判去了后者
51         return tree[node];
52     }
53     int mid = (start + end) / 2;
54     int left_node = node*2;
55     int right_node = node*2+1;
56     
57     int left_max = search_tree(start, mid, left_node, l, r);
58     int right_max = search_tree(mid+1, end, right_node, l, r);
59     int ans = max(left_max, right_max);
60     return ans;
61 }
62 
63 int main(){
64     while(scanf("%d%d", &n, &m) != EOF){
65         for(int i = 1; i <= n; i++)
66             scanf("%d", &grade[i]);
67         build_tree(1, n, 1);    
68         for(int i = 1; i <= m; i++){
69             char c;
70             int a, b;
71             scanf(" %c %d %d", &c, &a, &b);            //對于c語言的輸入字符在%c之前需要一個空格，否則c就讀取不到需要的字符了 
72             if(c == 'U') update_tree(1, n, 1, a, b);
73             else{
74                 int ans = search_tree(1, n, 1, a, b);
75                 printf("%d\n", ans);
76             }
77         }
78     }    
79     return 0;
80 }

HDU1166

題目分析：

也是一題線段樹的模板題，單點更新和區間查詢求和（本質上和區間求最大值是一樣的）

代碼：

 1 #include<iostream>
 2 #include<string>
 3 #include<string.h>
 4 using namespace std;
 5 
 6 const int N = 500005;
 7 int peo[N];
 8 int tree[N<<2];
 9 
10 void build_tree(int start, int end, int node){
11     if(start == end){
12         tree[node] = peo[start];
13     }else{
14         int mid = (start + end) / 2;
15         int left_node = node*2;
16         int right_node = node*2+1;
17         
18         build_tree(start, mid, left_node);
19         build_tree(mid+1, end, right_node);
20         tree[node] = tree[left_node] + tree[right_node];
21     }
22 }
23 
24 void update_tree(int start, int end, int node, int index, int value){
25     if(start == end){
26         tree[node] += value;
27     }else{
28         int mid = (start + end) / 2;
29         int left_node = node*2;
30         int right_node = node*2+1;
31         
32         if(index <= mid)
33             update_tree(start, mid, left_node, index, value);
34         else
35             update_tree(mid+1, end, right_node, index, value);
36         tree[node] = tree[left_node] + tree[right_node];    
37     }
38 }
39 
40 int query_tree(int start, int end, int node, int l, int r){
41     if(end < l || start > r){
42         return 0;
43     }else if(start >= l && end <= r){
44         return tree[node];
45     }else if(start == end){
46         return tree[node];
47     }
48     int mid = (start + end)    / 2;
49     int left_node = node*2;
50     int right_node = node*2+1;
51     
52     int left_sum = query_tree(start, mid, left_node, l, r);
53     int right_sum = query_tree(mid+1, end, right_node, l, r);
54     int ans = left_sum + right_sum;
55     return ans;
56 }
57 
58 int main(){
59     int t;
60     scanf("%d", &t);
61     int cnt = 1;
62     while(t--){
63         printf("Case %d:\n", cnt++);
64         int n;
65         scanf("%d", &n);
66         for(int i = 1; i <= n; i++)
67             scanf("%d", &peo[i]);
68         build_tree(1, n, 1);
69         string s;
70         int a, b;
71         while(cin>>s){
72             if(s == "End") break;
73             scanf("%d%d", &a, &b);
74             if(s == "Query"){
75                 int ans = query_tree(1, n, 1, a, b);    
76                 printf("%d\n", ans);
77             }
78             if(s == "Add"){
79                 update_tree(1, n, 1, a, b);
80             }
81             if(s == "Sub"){
82                 update_tree(1, n, 1, a, -b);
83             }
84         }
85     }
86     return 0;
87 } 

標籤：其他

上一篇：理解計算機記憶體、資料型別本質、連續存盤

下一篇：Codeforces Round #598 (Div. 3)- E. Yet Another Division Into Teams - 動態規劃