ACM模板库

ACM模板库


维护区间最小值ST表

<pre><code class="language-cpp">const int maxn = 3e5+5; int st[maxn][25]; int n ll a[maxn]; int lg[300005] = {-1}; void getlog(){ for(int i = 1; i &lt;= 300005; i++) lg[i] = lg[i/2] + 1; return; } void init(){ for(int i = 1; i &lt;= n; i++){ st[i][0] = a[i]; //st表存数组值 } for(int j = 1; (1 &lt;&lt; j) &lt;= n; j++){ for(int i = 1; i + (1 &lt;&lt; (j-1)) &lt;= n; i++){ st[i][j] = min(st[i][j-1], st[i+(1&lt;&lt;(j-1))][j-1]); //此条语句 } } } int query(int l, int r){ int k = lg[r-l+1]; return min(st[l][k], st[r-(1&lt;&lt;k)+1][k]); //此条语句 }</code></pre>

页面列表

ITEM_HTML