一种对区间查找树的递归转循环方法

最近在写BVH树的时候由于并行计算对递归的不友好,故只能找一种非递归方式替代我很肯定这个东西有它自己的名字，而且估计五十年前就已经被发现了，但我没找到相应资料 (Upd:翻了我三年前的B乎收藏夹,好像是叫morris遍历?🤔,22.05.09)

概述

思路很简单.每次要么走第一个子节点(对于二叉树就是左节点),要么走祖先节点中最近且仍有子节点未访问的节点的这个未访问的节点,这是可以通过预处理出来的

对比

除了能够针对并行程序或不支持递归的上古语言进行适配,减小栈调用外,其实在时间效率上并没有提升,甚至常数还比较大(递归的常数远比想象中的要小,至少在这种层数较小的情况下是这样) loj132中此种方法与BIT和普通线段树的对比而且如果用这种方法解决线段树问题的话也不能通过回溯维护信息,只能写标记永久化

实现

支持区间加,区间查询的线段树

int build(int l, int r, int nt) {
    int u = cnt++;
    T[u].nxt = nt;
    T[u].l = l; T[u].r = r;
    int mid = (l + r) >> 1;
    T[u].add = 0;
    if (l < r) {
        int rc = build(mid + 1, r, nt);
        T[u].lc = build(l, mid, rc);
        T[u].sum = T[T[u].lc].sum + T[rc].sum;
    }
    else
        T[u].sum = a[l];
    return u;
}
long long query(int l, int r) {
    int u = rt;
    long long res = 0;
    while (u != -1) {
        if (T[u].l > r || T[u].r < l) {
            u = T[u].nxt;
            continue;
        }
        res += (std::min(r, T[u].r) - std::max(l, T[u].l) + 1) * T[u].add;
        if (l <= T[u].l && T[u].r <= r) {
            res += T[u].sum;
            u = T[u].nxt;
            continue;
        }
        u = T[u].lc;
    }
    return res;
}
void modify(int l, int r, long long x) {
    int u = rt;
    while (u != -1) {
        if (T[u].l > r || T[u].r < l) {
            u = T[u].nxt;
            continue;
        }
        if (l <= T[u].l && T[u].r <= r) {
            T[u].add += x;
            u = T[u].nxt;
            continue;
        }
        T[u].sum += (std::min(r, T[u].r) - std::max(l, T[u].l) + 1) * x;
        u = T[u].lc;
    }
}