我们经常会用到这样的代码
if(mark[i])i++;//i--很明显，这个代码是用来在序列上寻找距离当前节点最近的没有被标记的节点 但这个代码复杂度为 O(n) ，有些时候并不见得能过时间复杂度 于是我们可以运用线段树的原理设计一个 O(logn2) 复杂度的算法来解决这个问题
我们用线段树的每个节点代表一个区间 在树上进行整个标记和查找的操作 在这棵树上操作时， 需要寻找的是在当前节点 A 之前的第一个没被标记过的节点B 很显然，如果当前区间全部被标记，需要继续 up 并且，我们肯定是从 LCA(A,B) 的右子树 up 上来 从它的左子树 down 下去的 于是，如果我们是从左子树 up 上来的，需要继续 up 同样的，如果当前节点的左子树已被标记，也还需要继续 up 至于 down 的操作就很无脑了 而找到了这个点之后就可以在树上对其进行标记操作
代码如下：
int tree[M<<2],A[M],B[M<<2]; //A代表序列中的点在树上的编号 //B代表树上的点在序列中的编号 //tree代表序列上某一区间是否全部被标记 void build(int l,int r,int p){ if(l==r){ A[l]=p; B[p]=l; return; } int mid=l+r>>1; build(l,mid,(p<<1)); build(mid+1,r,(p<<1)|1); } int query(int p){ if(tree[p]){ int pre=p;p>>=1; while(tree[p<<1]||pre==(p<<1)){ //①区间所有点都被标记过(包含于第②种情况，可以忽略)②该区间的左子树中的点都被标记过③先前是从左子树中up上来的 //这三种情况则需要继续up pre=p; p>>=1; } p<<=1; while(p&&!B[p]){ if(tree[(p<<1)|1])p<<=1; else p=(p<<1)|1; } } return p; } void update(int p){ do tree[p]=1,p>>=1; while(!tree[p]&&tree[p<<1]&&tree[(p<<1)|1]); }