Segment Tree

• เอามาจาก wiki.acioi.in.th

 1  
 2 #include<stdio.h>
 3  #define INF 1000000001
 4  int arr[1005],st[2005],n;	//st = segment tree
 5  void build(int s,int t,int x,int *A)
 6  {
 7  	if(s==t)
 8  	{
 9  		st[x]=A[s];
10  		return;
11  	}
12  	int mid =(s+t)/2;
13  	build(s,mid,2*x,A);
14  	build(mid+1,t,2*x+1,A);
15  	//sum
16  	st[x]=st[2*x]+st[2*x+1];
17  	/*min
18  	if(st[2*x]<st[2*x+1])	st[x]=st[2*x];
19  	else	st[x]=st[2*x+1];
20  	*/
21  	/*max
22  	if(st[2*x]>st[2*x+1])	st[x]=st[2*x];
23  	else	st[x]=st[2*x+1];
24  	*/
25  }void build(int *A)	{	build(1,n,1,A);	}
26  
27  void update(int s,int t,int x,int idx,int val)
28  {
29  	if(s==t)
30  	{
31  		st[x]=val;
32  		return;
33  	}
34  	int mid=(s+t)/2;
35  	if(idx<=mid)	update(s,mid,2*x,idx,val);
36  	else	update(mid+1,s,2*x+1,idx,val);
37  	//sum
38  	st[x]=st[2*x]+st[2*x+1];
39  	/*min
40  	if(st[2*x]<st[2*x+1])	st[x]=st[2*x];
41  	else	st[x]=st[2*x+1];
42  	*/
43  	/*max
44  	if(st[2*x]>st[2*x+1])	st[x]=st[2*x];
45  	else	st[x]=st[2*x+1];
46  	*/
47  }
48  void update(int idx,int val)	{	arr[idx]=val;	update(1,n,1,idx,val);	}
49  
50  int find(int s,int t,int x,int i,int j)
51  {
52  	if(t<i || s>j)	return -INF;	//non intersect
53  	if(s>=i && t<=j)	return st[x];	// is subset
54  	int mid=(s+t)/2;
55  	int p=find(s,mid,2*x,i,j);
56  	int q=find(mid+1,t,2*x+1,i,j);
57  	if(p==-INF)	return q;
58  	if(q==-INF)	return p;
59  	//sum
60  	return p+q;
61  	/*min
62  	if(p<q)	return p;
63  	else	return q;
64  	*/
65  	/*max
66  	if(p>q)	return p;
67  	else	return q;
68  	*/
69  }
70  int find(int i,int j)	{	return find(1,n,1,i,j);	}