区间树上查找所有与给定区间相交的区间-算法复杂度正确性证明-526互联

区间树是在平衡树上维护的数据结构，按照左端点大小排序。详见《算法导论》。

算法设计思路

红黑树的拓展

在红黑树上维护结点属性$min, max$：

$min$表示该结点及其所有后代结点中的区间低端的最小值。

$max$表示该结点及其所有后代结点中的区间高端的最大值。

在插入时，对结点路上经过的所有结点的$min,max$值进行更新。

在插入后的调整时，在rotate函数中对旋转后结点的$min,max$值进行更新维护。

查找算法

剪枝：

根据一个结点$x$上的$x.min,x.max$属性，由$x.min,x.max$的定义可以知道：

区间$[a, b]$与$[x.min, x.max]$不相交，则$x$和$x$的所有后代结点都不与$[a, b]$相交。

证明：假设以$x$为根的子树中存在结点$y$，$y$中所包含的$[y.low, y.high]$区间与$[a, b]$相交。则要么$y.low < b$，要么$y.high > a$。则$x.min \le y.low < b$或$x.max >= y.high > a$。这与$[a, b]$和$[x.min, x.max]$不相交矛盾。

此时可以进行剪枝，不探索以$x$为根的子树。

查找算法：

根据以上的剪枝原则，对整个区间树进行遍历，要剪枝的结点则不进行遍历。因为剪枝剪掉的子树内不可能有答案，所以这个遍历的算法可以保证输出所有的答案。

下面是对算法时间复杂度的证明：

考虑$[a, b]$与$[x.min, x.max]$相交，但$x$的子树内无答案的情况。为简便，记满足条件“$[a, b]$与$[x.min, x.max]$相交，但$x$的子树内无答案“为满足性质A。

首先，$x.min, x.max$两个值不会在区间$[a, b]$内，否则$x$子树内必然存在某一结点$y$，满足$y.low = x.min$或者$y.high = x.max$，由此得出$y$的区间与$[a, b]$相交，与假设矛盾。

又由$x.min < x.max$，$[a, b]$与$[x.min, x.max]$相交两个条件，所以只有一种情况：

\[x.min < a \le b < x.max \]

以上这个性质是性质A的推论。

记$x$的两个孩子为$xl $和$xr$，则两个孩子的$[min, max]$区间至多有一个与$[a, b]$相交，以下证明：

如果$xl.max > b$，则说明在$xl$的子树内存在一个结点$y$，满足$y.high = xl.max > b$。因为$y$的区间不与$[a, b] $相交，则必然有$y.low > b$。由于区间树的性质，$xr$子树中的任意一点$z$都有$z.low > y.low > b$，则必然有$xr.min > b$。

即，如果$xl$的$[xl.min, xl.max]$与$[a, b]$相交，则$xr$的就不可能与$[a, b]$相交。

这个结论的逆否命题也是正确的：如果$xr$的$[xr.min, xr.max]$与$[a, b]$相交，则$xl$的就不可能与$[a, b]$相交。

综合这两条，所以两个孩子的$[min, max]$区间至多有一个与$[a, b]$相交，而这个孩子也是满足性质A的。

所以，对于$x$的子树的搜索，每一层只会向其中一个孩子进行搜索，搜索的结点个数为$x$的子树的深度，即$O(\log n)$。

最终，算法在$x$的子树中的搜索会停在这样一个结点$z$：z本身满足性质A，$z$的左孩子$zl$满足$zl.max < a$，$z$的右孩子$zr$满足$zr.min > b$。

这样的结点$z$整棵树只会有一个，下面是证明。

假设存在另一个结点$z'$，满足：$z'.min < a \le b < z'.max$，$z'$的左孩子$zl'$满足$zl'.max < a$，$z$的右孩子$zr'$满足$zr'.min > b$.

首先由$min,max$两个属性的性质可以确定，$z$和$z'$之间，没有一个点为另一个点的祖先的情况。

其次，如果$z$在中序遍历中比$z'$靠前，则必然有$zr.min < zl'.min$。然而，又有$zr.min > b, zl'.min \le zl'.max < a \le b$。产生矛盾。

同理，$z$在中序遍历中比$z'$靠后也会产生矛盾。

综上，$z$这样性质的点在树中是唯一的。

对于$x$的任意祖先$g$，有$g.min \le x.min < a \le b < x.max \le g.max$。而且存在一个唯一的祖先$g^*$，满足：$g^*$的子树内没有答案，且（$g^*$是根节点或$g^*$的所有祖先的子树内有答案）。

因为$z$的唯一性，同时所有满足性质A的结点都是$z$的祖先，所以从$z$向祖先方向追溯一定会找到这个$g^*$，而且$g^*$也是唯一的。

综上所述，在搜索过程中，满足性质A的结点在整棵树的搜索过程中最多只会遇到一次，而且在这个结点的子树中会遍历$O(\log n)$个结点。

除了如上所述的情况以外，该搜索算法只会遍历集合$A=\{结点x|x的子树内有答案\}$中的点。因为集合$A$由所有的答案，以及所有答案的祖先构成，所以$|A|=O(\min(n, k\log n))$。

在每一个结点上消耗的时间是$O(1)$的。

综上所述，搜索的总时间复杂度为：

\[T(n) = O(\min(n, k\log n))+O(\log n)=O(\min(n, k\log n)) \]

算法实现

复制红黑树的实现代码，并对其作出修改。主要的修改是添加对min, max两个属性的维护。

数据结构的定义：

// 定义区间
struct Interval {
    int l, r;
    Interval() {
        l = r = 0;
    }

    Interval(int _l, int _r) {
        l = _l;
        r = _r;
    }
	// 在红黑树中的排序方式
    bool operator < (const Interval &b) const {
        return l < b.l;
    }
};

struct TNode {
    int color;
    Interval key;  // key为区间
    int max, min;  // 新添加的属性
    TNode *left;
    TNode *right;
    TNode *p;
    static const int LEFT = 0, RIGHT = 1;
    static const int RED = 2, BLACK = 3;
} node[MAXN], *root = NULL, *nil = NULL;

实现维护min, max属性的代码，并添加进rotate函数里。

void rotate(TNode *x, int side) {
    TNode *ch, *g, *cou;
    if (side == TNode :: LEFT) {
        ch = x->right, g = x->p, cou = ch->left;
        if (g != nil) {
            if (isLeftCh(x)) {
                g->left = ch;
            } else {
                g->right = ch;
            }
        }
        ch->p = g;

        x->p = ch;
        ch->left = x;
        
        x->right = cou;
        if(cou != nil) cou->p = x;
    } else {
        ch = x->left, g = x->p, cou = ch->right;
        if (g != nil) {
            if (isLeftCh(x)) {
                g->left = ch;
            } else {
                g->right = ch;
            }
        }
        ch->p = g;

        x->p = ch;
        ch->right = x;
        
        x->left = cou;
        if (cou != nil) cou->p = x;
    }
    if (ch->p == nil)
        root = ch;
    update(x); // 更新min，max
    update(ch); // 更新min, max
}

在insert的路上更新min, max。

void insert(Interval val) {
    TNode *y = nil;
    TNode *x = root;
    TNode *z = new TNode;
    z->key = val;
    z->max = val.r;
    z->min = val.l;
    z->p = z->left = z->right = nil;
    z->color = TNode :: RED;
    while (x != nil) {
        y = x;
        x->max = max(x->max, z->key.r); // 更新max
        x->min = min(x->min, z->key.l); // 更新min
        if (z->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }
    z->p = y;  
    if (y == nil) {
        root = z;
        return ;
    }
    if (z->key < y->key) {
        y->left = z;
    } else {
        y->right = z;
    }
    insertFix(z);
}

搜索算法，使用中序遍历。

bool overlap(Interval a, Interval b) {
    return a.r >= b.l && b.r >= a.l;
}

bool intervalSearch(TNode *p, Interval x) {
    bool flag = false;
    if (p->left != nil && p->left->max >= x.l)
        flag |= intervalSearch(p->left, x);
    if (overlap(p->key, x)) {
        printf("[%d, %d]\n", p->key.l, p->key.r);
        flag = true;
    }
    if (p->right != nil && p->right->min <= x.r) 
        flag |= intervalSearch(p->right, x);
    return flag;
}