https://wiki.ta.in.th/index.php?action=history&feed=atom&title=Segment_Tree 2026-06-16T22:58:05Z Revision history for this page on the wiki MediaWiki 1.33.0-alpha https://wiki.ta.in.th/index.php?title=Segment_Tree&diff=33&oldid=prev 2019-03-06T17:24:14Z

<p>Created page with &quot;* เอามาจาก wiki.acioi.in.th &lt;syntaxhighlight lang=&quot;c++&quot; line=&#039;line&#039;&gt; #include&lt;stdio.h&gt; #define INF 1000000001 int arr[1005],st[2005],n; //st = segment tree...&quot;</p> <p><b>New page</b></p><div>* เอามาจาก wiki.acioi.in.th<br /> &lt;syntaxhighlight lang=&quot;c++&quot; line='line'&gt; <br /> #include&lt;stdio.h&gt;<br /> #define INF 1000000001<br /> int arr[1005],st[2005],n; //st = segment tree<br /> void build(int s,int t,int x,int *A)<br /> {<br /> if(s==t)<br /> {<br /> st[x]=A[s];<br /> return;<br /> }<br /> int mid =(s+t)/2;<br /> build(s,mid,2*x,A);<br /> build(mid+1,t,2*x+1,A);<br /> //sum<br /> st[x]=st[2*x]+st[2*x+1];<br /> /*min<br /> if(st[2*x]&lt;st[2*x+1]) st[x]=st[2*x];<br /> else st[x]=st[2*x+1];<br /> */<br /> /*max<br /> if(st[2*x]&gt;st[2*x+1]) st[x]=st[2*x];<br /> else st[x]=st[2*x+1];<br /> */<br /> }void build(int *A) { build(1,n,1,A); }<br /> <br /> void update(int s,int t,int x,int idx,int val)<br /> {<br /> if(s==t)<br /> {<br /> st[x]=val;<br /> return;<br /> }<br /> int mid=(s+t)/2;<br /> if(idx&lt;=mid) update(s,mid,2*x,idx,val);<br /> else update(mid+1,s,2*x+1,idx,val);<br /> //sum<br /> st[x]=st[2*x]+st[2*x+1];<br /> /*min<br /> if(st[2*x]&lt;st[2*x+1]) st[x]=st[2*x];<br /> else st[x]=st[2*x+1];<br /> */<br /> /*max<br /> if(st[2*x]&gt;st[2*x+1]) st[x]=st[2*x];<br /> else st[x]=st[2*x+1];<br /> */<br /> }<br /> void update(int idx,int val) { arr[idx]=val; update(1,n,1,idx,val); }<br /> <br /> int find(int s,int t,int x,int i,int j)<br /> {<br /> if(t&lt;i || s&gt;j) return -INF; //non intersect<br /> if(s&gt;=i &amp;&amp; t&lt;=j) return st[x]; // is subset<br /> int mid=(s+t)/2;<br /> int p=find(s,mid,2*x,i,j);<br /> int q=find(mid+1,t,2*x+1,i,j);<br /> if(p==-INF) return q;<br /> if(q==-INF) return p;<br /> //sum<br /> return p+q;<br /> /*min<br /> if(p&lt;q) return p;<br /> else return q;<br /> */<br /> /*max<br /> if(p&gt;q) return p;<br /> else return q;<br /> */<br /> }<br /> int find(int i,int j) { return find(1,n,1,i,j); }<br /> &lt;/syntaxhighlight&gt;</div>

Tata