格子游戏

题目链接： http://exercise.acmcoder.com/online/online_judge_ques?ques_id=1662&konwledgeId=135
解题思路：线段树。
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int MAXN=100005;
 5 typedef long long LL;
 6 
 7 struct Node
 8 {
 9     int l,r;
10     long long sum;
11     long long Max;
12     Node():l(0),r(0),sum(0LL){}
13 }f[4*MAXN];
14 
15 int a[MAXN];
16 int n,m;
17 
18 void pushUp(int t)
19 {
20     f[t].sum=f[2*t].sum+f[2*t+1].sum;
21     f[t].Max=max(f[2*t].Max,f[2*t+1].Max);
22 }
23 void build(int t,int l,int r)
24 {
25     f[t].l=l;
26     f[t].r=r;
27     if (l==r) {f[t].sum=a[l];f[t].Max=a[l];return;}
28     int mid=(l+r)/2;
29     build(2*t,l,mid);
30     build(2*t+1,mid+1,r);
31     pushUp(t);
32 }
33 
34 void modify(int t,int l,int c)
35 {
36     if (f[t].l==l && f[t].r==l)
37     {
38         f[t].sum=c;f[t].Max=c;
39         return;
40     }
41     int mid=(f[t].l+f[t].r)/2;
42     if (l<=mid)modify(2*t,l,c);
43     else modify(2*t+1,l,c);
44     pushUp(t);
45 }
46 
47 LL query(int t,int l,int r)
48 {
49     if (f[t].l==l && f[t].r==r)
50     {
51         return f[t].sum;
52     }
53     int mid=(f[t].l+f[t].r)/2;
54     if (r<=mid) return query(2*t,l,r);
55     else if (l>mid) return query(2*t+1,l,r);
56     else return query(2*t,l,mid)+query(2*t+1,mid+1,r);
57 }
58 
59 LL queryMax(int t, int l,int r)
60 {
61     if (f[t].l==l && f[t].r==r)
62     {
63         return f[t].Max;
64     }
65     int mid=(f[t].l+f[t].r)/2;
66     if (r<=mid) return queryMax(2*t,l,r);
67     else if (l>mid) return queryMax(2*t+1,l,r);
68     else return max(query(2*t,l,mid),query(2*t+1,mid+1,r));
69 }
70 
71 int main()
72 {
73 #ifndef ONLINE_JUDGE
74     freopen("test.txt","r",stdin);
75 #endif // ONLINE_JUDGE
76     while(cin>>n>>m)
77     {
78         for (int i=1;i<=n;++i) scanf("%d",&a[i]);
79         build(1,1,n);
80         int op,x,y;
81         for(int i=1;i<=m;++i)
82         {
83             cin>>op>>x>>y;
84             if (op==1) modify(1,x,y);
85             else if (op==2) printf("%lld
", query(1,x,y));
86             else printf("%lld
", queryMax(1,x,y));
87         }
88     }
89     return 0;
90 }