Segment Tree

gistfile1.txt

给定一个整数N，比如N=100，有如下的初始有序序列位于[0，N-1]之间 [0 1] [4 5 6] [9 10 11] [20] [98 99]。设计一个数据结构保存这个初始序列，然后写一个函数，接受一个参数x，满足0<=x<=N-1，1)若x在该结构中不存在，出错；2)若x存在，返回x之后第一个不存在的数，并把该数写入结构中

segment tree.c

 typedef node{
     int left;
     int right;
     int delta;
     int sum;
     node* lchild;
     node* rchild;
 };

 void build(node* cur, int l, int r){
     cur.left = l;
     cur.right = r;

     if (r == l + 1){
         cur.lchild = NULL;
         cur.rchild = NULL;
         cur.delta = 0;
         cur.sum = 0;
     }else{
         cur.lchild = new node;
         cur.rchild = new node;
         build(cur.lchild, l, ((l&r)+((l^r)>>1)) );
         build(cur.rchild, ((l&r)+((l^r)>>1))+1, r);
     }
 }

 void update(node* cur, int l, int r, int dic){
     node* lc = cur.lchild;
     node* rc = cur.rchild;
     if (l <= cur.left && cur.right <= r){
         if(0 == dic){
             --cur.delta;
         }else{
             ++cur.delta;
         }
     }else{
         if (l <= ((l&r)+((l^r)>>1)))
             update(lc, l, r, dic);
         if (r > ((l&r)+((l^r)>>1)))
             update(rc, l, r, dic);

         if (lc.delta > 0)
             cur.sum = lc.right - lc.left;
         else
             cur.sum = lc.sum
         if(rc.delta > 0)
             cur.sum = cur.sum + rc.right - rc.left;
         else
             cur.sum = cur.sum + rc.sum;
     }
 }