概述
高斯消元的时间复杂度为 $O(n^3)$。
对于条带状矩阵，即满足对于任意 $i$，从 $(i,i)$ 向右拓展有不超过 $d-1$ 个数字，向下拓展有不超过 $d-1$ 个数字的矩阵。可以做到 $O(nd^2)$。
实现是简单的，类似高斯消元，限制范围即可。需要注意的是，当主元为 $0$ 时需要换行，那么消元时需要向右消 $2d$ 个位置。
例题
-
DP，只有 $x^2+y^2 \le R^2$ 的不为 $0$，有 $O(R^2)$ 个点。
连续标号，那么是一个满足 $d=R+1$ 的矩阵，消元时间复杂度 $O(R^4)$。
-
矩阵是下三角的，反着消变为上三角的，时间复杂度 $O(n^2d)$。