logtrick
Logtrick是一种针对子数组位运算、gcd等操作的高效优化算法，通过利用或运算只增不减的性质，将以固定左端点为起点的所有子数组的按位或结果数量限制在不超过二进制位数，并且相同结果对应连续的右端点区间。文章以“按位或最大的最小子数组长度”问题为例，先给出暴力O(n²)解法，再介绍两种Logtrick实现：一种倒序遍历并合并相同或值、保留最小右端点；另一种利用集合子集关系正向剪枝，提前跳出无效循环。两种方法都将复杂度降至O(n log U)，巧妙解决了大数据规模下的子数组最值计数问题。