倍增与 ST 表

倍增

倍增即成倍增长。是指我们在进行递推时，如果状态空间很大，线性递推无法满足时空要求，此时可以考虑成倍增长的方式，只递推状态空间在 $2$ 的整数次幂位置上的值作为代表，其他值可以通过“任意整数可以表示成若干个 $2$ 的次幂项的和”这一性质得到。

算法竞赛进阶指南原书例题：给定一个长度为 $N$ 的数列 $A$，然后进行若干次询问，每次给定一个整数 $T$，求出最大的 $k$，满足 $\sum _{i=1}^{k}A[i]\le T$。

倍增算法：

1. 令 $p=1,k=0,sum=0$
2. 比较“$A$ 数组中 $k$ 之后的 $p$ 个数的和”与 $T$ 的大小，也就是说，如果 $sum+S[k+p]-S[k]\le T$，则令 $sum+=S[k+p]-S[k],k+=p,p\ast =2$，即累加上这 $p$ 个数的和，然后把 $p$ 的跨度增长一倍。否则 $p/=2$。
3. 当 $p$ 为 $0$ 时，结束循环，此时 $k$ 即为答案。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, a[N], t, s[N];

int main() {
	cin >> n >> t;
	for(int i = 1; i <= n; i++) {
        cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}

	int p = 1, k = 0, sum = 0;
	while(p) {
		if (k + p <= n && sum + s[k + p] - s[k] <= t) {
			sum += s[k + p] - s[k];
			k += p;
			p *= 2;
		} else {
			p /= 2;
		}
	}

	cout << k << endl;

	return 0;
}

问题思考：AcWing 109. 天才 ACM

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e6 + 10;
ll t, n, m, K, a[N], tot, b[N];

bool calc(ll l,ll k,ll p) {
	ll res = 0;
	for(ll i = l; i <= k + p; i++) b[i - l] = a[i];

    ll len = p + k - l + 1;
	sort(b, b + len);

    if (len >= 2 * m) {
		for(ll i = 0; i < m; i++) {
			res += (b[i] - b[len - i - 1]) * (b[i] - b[len - i - 1]);
		}
	} else {
		ll temp = len / 2;
		for(ll i = 0; i < temp; i++) {
			res += (b[i] - b[len - i - 1]) * (b[i] - b[len - i - 1]);
		}
	}

	if (res <= K) return true;
	return false;
}

int main() {
	cin >> t;
	while (t--) {
		tot = 0;
		cin >> n >> m >> K;

		for (ll i = 0; i < n; i++) cin >> a[i];

		ll l = 0;
		while (l < n) {
			ll k = l, p = 1;
			while (p) {
				if (calc(l, k, p) && k + p < n) {
					k += p;
					p *= 2;
				} else {
					p /= 2;
				}
			}
			tot++;
			l = k + 1;
		}
		cout << tot << endl;
	}

	return 0;
}

ST 表

ST 表（Sparse Table，稀疏表）是用于解决可重复贡献问题的数据结构。

例如：给定 $n$ 个数， $m$ 个询问，对于每个询问，求解区间 [l, r] 的最大值。

朴素想法：考虑使用区间 DP，

1. 枚举所有的左端点和右端点，记录所有区间的最大值，用 f[i][j] 来表示区间 [i, j] 的最大值。
2. 状态转移，考虑当前状态 f[i][j] 由何状态转变而来？当前区间 [i][j] 最后加入进来的值可能时 $a_i$ 也可能是 $a_j$
   1. 选 $a_i$：f[i][j] = max(f[i + 1][j], a[i])
   2. 选 $a_j$：f[i][j] = max(f[i][j - 1], a[j])
3. 状态转移方程：f[i][j] = max(max(f[i][j - 1], a[j]), max(f[i + 1][j], a[i]))
4. 边界条件：i == j 时 f[i][j] = a[i]

5. for (int len = 1; len <= n; len++) { // 区间长度
   	for (int i = 1; i + len - 1 <= n; i++) { // 左端点
   		int j = i + len - 1; // 右端点
   		if (i == j) f[i][j] = a[i];
   		else f[i][j] = max(max(f[i][j - 1], a[j]), max(a[i], f[i + 1][j]));
   	}
   }

6. 问题与思考：时间复杂度？空间复杂度？有没有更好的状态表示？

算法思想

ST 表基于倍增思想，预处理时间复杂度为 $O(n\log n)$，查询 $O(1)$。ST 表不支持修改操作。

具体实现如下：

预处理

1. 令 $f(i,j)$ 表示区间 $[i,i+2^j-1]$ 的最大值，$f(i,0)=a_i$。
2. 状态转移方程：$f(i,j)=max(f(i,j-1),f(i+2^{j-1},j-1))$。

查询

对于每一个询问，可以将其分成两部分：$[l,l+2^k-1]$ 与 $[r-2^k+1,r]$，这里的 $k=\lfloor {\log }_{2}r-l+1\rfloor$

算法实现

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

const int N = 1e5 + 10, M = 18;
int a[N], f[N][20], n, m, lg2[N];

void init() {
	for (int j = 0; j < M; j++) {
		for (int i = 1; i + (1 << j) - 1 <= n; i++) {
			if (!j) f[i][j] = a[i];
			else f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
		}
	}
}

int query(int l, int r) {
	int k = lg2[r - l + 1];
	// 使用cmath 中的 log函数 以10为底
	// int k = log(r - l + 1) / log(2);

	return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main() {
	scanf("%d%d", &n, &m);

	for (int i = 2; i <= n; i++) lg2[i]= lg2[i >> 1] + 1;

	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	init();

	while (m--) {
		int x, y; scanf("%d%d", &x, &y);
		printf("%d\n", query(x, y));
	}

	return 0;
}

注意：可以预处理 $\log$

$$\begin{array}{r}\{\begin{array}{lll}{\log }_{2}1& =0& (n=1)\\ {\log }_{2}n& ={\log }_2\frac{n}{2}+1& (n\ge 2)\end{array}\end{array}$$

• ${\log }_{2}n={\log }_2(2\ast \frac{n}{2})={\log }_{2}2+{\log }_2\frac{n}{2}=1+{\log }_2\frac{n}{2}$