线段树模板

 1 struct node
 2 {
 3     int maxt,sum;
 4     int left,right;
 5 };
 6 struct node tree[4*K];
 7 int a[k];
 8 int build(int id,int l,int r)
 9 {
10     tree[id].left=l;tree[id].right=r;
11     if(l==r)
12     {
13         tree[id].maxt=tree[id].sum=a[l];
14     }
15     else
16     {
17         build(2*id,l,(l+r)/2);
18         build(2*id+1,(l+r)/2+1,r);
19         tree[id].maxt=max(tree[2*id].maxt,tree[2*id+1].maxt);
20         tree[id].sum=tree[2*id].sum+tree[2*id+1].sum;
21     }
22     return 0;
23 }
24 long long queryMax(int id,int l,int r)
25 {
26     if(l==tree[id].left && r==tree[id].right)
27         return tree[id].maxt;
28     int mid=(tree[id].left+tree[id].right)>>1;
29     long long ret=0;
30     if(r<=mid)
31         ret=max(ret,queryMax(id<<1,l,r));
32     else if(l>=mid+1)
33         ret=max(ret,queryMax((id<<1)+1,l,r));
34     else
35     {
36         long long a,b;
37         a=queryMax(id<<1,l,mid);
38         b=queryMax((id<<1)+1,mid+1,r);
39         return max(a,b);
40     }
41     return ret;
42 }
43 int update(int id,int pos,int v)
44 {
45     if(tree[id].left == tree[id].right)
46     {
47         tree[id].sum=tree[id].maxt=v;
48     }
49     else
50     {
51         int mid=(tree[id].left+tree[id].right)/2;
52         if (pos<=mid) update(id*2,pos,v);
53     else update(id*2+1,pos,v);
54         tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
55         tree[id].maxt=max(tree[id*2].maxt,tree[id*2+1].maxt);
56     }
57     return 0;
58 }
59 
60 int query(int id,int l,int r)
61 {
62         if (tree[id].left==l&&tree[id].right==r)
63             return tree[id].sum; 
64         else
65         {
66             int mid=(tree[id].left+tree[id].right)/2;    
67             if (r<=mid) return query(id*2,l,r);
68             else if (l>mid) return query(id*2+1,l,r)
69             else return query(id*2,l,mid)+query(id*2+1,mid+1,r);
70         }
71     }
记得有个小地方打错变量名了，要用的话自己改下就好