继 ST 表, zkw 线段树后，发现了一种新的解法——猫树

维护静态线段树，使得普通查询复杂度为 O(1)

对查询的叶子节点 l,r ，求出 LCA ，那么 l,r 一定分别是它的左儿子和右儿子。如果对每个节点维护 mid 为起点的右子前缀和、左子后缀和，那么就可以在 LCA 上 O(1) 计算答案。空间复杂度升为 O(n\log n) (主定理可知)

若线段树是满二叉树，那么二进制最长公共前缀 LCP(x,y)=x>>\log(x\oplus y) ，而 LCA 就是 LCP，预处理 log 即可 O(1) 求 LCA 。

实现：建树可以不建叶子节点(那么查询叶子节点要特判)。建树时先求出 mid 信息，然后暴力向左向右拓展后缀/前缀和(因为深度为 \log n ，所以开 n\times \log n 空间即可)。建树时对每个下标求出线段树叶子节点编号，记作 pos[i] ，那么 LCA 的深度(假设从 1 开始)可以表示为 \log(pos[r])-\log(pos[l]\oplus pos[r]) 。查询时对这个深度的前缀和、后缀和合并即可。

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%lld", &x)
typedef long long ll;
#define mn 131082 // 1<<log(1e5,2)+10
#define ml 20
ll n, m, a[mn], n2, lg[mn * 2], l, r;
ll pos[mn], gcd[mn][ml];
#define lfs p << 1
#define rfs p << 1 | 1
#define mkcf ll cf = (lf + rf) >> 1
void build(ll p, ll lf, ll rf, ll dep)
{
    if (lf == rf)
    {
        pos[lf] = p;
        return;
    }
    mkcf;
    build(lfs, lf, cf, dep + 1);
    build(rfs, cf + 1, rf, dep + 1);
    gcd[cf][dep] = a[cf];
    for (ll i = cf - 1; i >= lf; --i)
    {
        gcd[i][dep] = __gcd(gcd[i + 1][dep], a[i]);
    }
    for (ll i = cf + 1; i <= rf; ++i)
    {
        gcd[i][dep] = __gcd(gcd[i - 1][dep], a[i]);
    }
}
signed main()
{
    sc(n), sc(m);
    for (ll i = 1; i <= n; ++i)
    {
        sc(a[i]);
    }
    for (n2 = 1; n2 < n; n2 <<= 1) //满二叉下节点有n2个
        ;
    for (ll i = 2; i <= n2 * 2; ++i)
    {
        lg[i] = lg[i / 2] + 1;
    }
    build(1, 1, n2, 1);
    while (m--)
    {
        sc(l), sc(r);
        if (l == r) //猫树不存叶子节点
        {
            printf("%lld\n", a[l]);
            continue;
        }
        ll k = lg[pos[r]] - lg[pos[l] ^ pos[r]];
        printf("%lld\n", __gcd(gcd[l][k], gcd[r][k]));
    }
    return 0;
}