c++线段树算法

电脑

c++

构造线段树，下面给出代码： •void build(int node, int l, int r)  {      if (l == r)          segTree[node] = array[l];   /* 若只有一个元素,节点记录该单元素 */     else{               /* 递归构造左右子树 */            build(2*node, l, (l+r)/2);                     build(2*node+1, (l+r)/2+1, r);   /* 回溯时得到当前node节点的线段信息并进行要求操作 如下为求区间最小值*/  if (segTree[2 * node] <= segTree[2 * node + 1])            segTree[node] = segTree[2 * node];         else            segTree[node] = segTree[2 * node + 1];      }  }

区间查询：   int query (int node, int l, int r, int left, int right) {    int p1, p2;/*判断查询区间（light--right）是否包含于被查询区间（l—r）*/   if (left > r || right < l)             return -1;       /*如果当前间隔包含在区间内* /  / *查询间隔返回SegTree [node]*/   if (l >= left && r <= right)             return segTree[node];       /*计算子区间内的最小值*/    p1 = query(2 * node, l, (l + r) / 2, left, right);    p2 = query(2 * node + 1, (l + r) / 2 + 1, r, left, right);       if (p1 == -1)return p2;  if (p2 == -1) return p1;      if (p1 <= p2) return  p1;   return  p2;      }

删除节点 void Del(int v,int L,int R) {     if(L>Tree[v].b||R=Tree[v].b){Tree[v].c-- ;return;}    //完全包含   Del(2*v, L,R); //遍历左子树   Del(2*v+1, L,R); //遍历右子树 }

单点修改 void Updata(int node, int l, int r, int ind, int add) /*单节点更新*/   {       if( l== r )     {         segTree[node] += add;        return ;      }   int m = ( left + right ) >> 1;   if(ind <= m) Updata(node * 2,left, m, ind, add);   else Updata(node * 2 + 1, m + 1, right, ind, add);   /*回溯更新父节点*/   segTree[node] = min(segTree[node * 2], segTree[node * 2 + 1]);   }