首页 > 代码库 > 线段树

线段树

【线段树的定义】

     有时候我们经常会碰到一些跟区间有关的问题,比如给一些区间线段求并区间的长度,或者并区间的个数等等。这些问题的描述都非常简单,但是通常情况下数据范围会非常大,而朴素方法的时间复杂度过高,导致不能在规定时间内得到问题的解。这时,我们需要一种高效的数据结构来处理这样的问题,我们介绍一种基于分治思想的数据结构--线段树。
     从简单说起,线段树其实可以理解成一种特殊的二叉树。但是这种二叉树较为平衡,和静态二叉树一样,都是提前已经建立好的树形结构。针对性强,所以效率要高。线段树是建立在线段的基础上,每个结点都代表了一条线段 [a , b]。长度为1的线段成为元线段。非元线段都有两个子结点,左结点代表的线段为[a , (a + b ) / 2],右结点代表的线段为[( a + b ) / 2 +1, b]。
下面看一个实例:
上图就是范围为[1,10]的线段树。根节点代表[1,10]区间,左孩子[1,5],右孩子[6,10]....依次类推,叶子节点代表的是长度为1的区间。
 【简单线段树的建立,查询,更新】
一 建立寻找区间最大值的线段树
1.线段树的建立:
 1 void bulid_tree(int rt,int L,int R)//构造线段树的过程相当于后序遍历 2 { 3     if(L==R) cin>>Max[rt];//说明到了叶节点,输入叶节点的值,Max数组存储的是各区间段的最大值 4     else 5     { 6         int mid=(L+R)/2; 7         build_tree(2*rt,L,mid);//递归构造左子树 8         build_tree(2*rt+1,mid+1,R);//递归构造右子树 9         Max[rt]=max(Max[2*rt],Max[2*rt+1]);//寻找根节点的值,左右儿子的较大值10     }11 }

2.线段树的更新:类似二分

 1 void  update(int r,int L,int R) 2 { 3     int mid=(L+R)/2; 4     if(L==R) Max[r]=v;//如果该点就是叶节点的话就把值更新,此时通过二分就找到了p,且p=L=R 5     else 6     { 7        if(p<=mid) update(2*r,L,mid);//如果查询点P在区间以左,则递归查询左区间 8        else  update(2*r+1,mid+1,R);//如果查询点p在区间以右,则递归查询右区间 9        Max[r]=max(Max[2*r],Max[2*r+1]);//更新并求得父节点最大值10     }11 }

3.线段树的查询:(以下函数只支持单点查询)

1 int query(int r,int ql,int qr)//查询操作2 {3     int mid=(L+R)/2;4     if(ql<=L&&qr>=R) return Max[r];//[ql,qr]包含区间[L,R]5     else if(qr<=mid) return query(2*r,L,mid);//[ql,qr]在区间[L,R]以左6     else if(ql>mid) return query(2*r+1,mid+1,R);//[ql,qr]在区间[L,R]以右7     else8         return max(query(2*r,L,mid),query(2*r+1,mid+1,R));//ql在区间[L,R]中点以左,qr在区间中点以右9 }

【复杂线段树的建立】

维护一个只有0和1的整数数列,支持四种操作:
①将[x,y]区间内的整数都变为0;
②将[x,y]区间内的整数都变为1;
③将[x,y]区间内所有0都变成1,所有1都变成0。
④查询区间[x,y]内1的个数。
一共有N个整数共执行M次操作。(N, M均为10^5级别)
 
1.线段树的建立:
// 更新父节点信息的update函数
void update(int cur)
{
    int ls = cur << 1, rs = cur << 1 | 1;
    ones[cur] = ones[ls] + ones[rs];
}
 
// 建立线段树
void build(int cur, int x, int y)
{
    int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1;
    to[cur] = -1, rev[cur] = 0;//to数组是用来判断是否被懒惰标记,rev数组是用来判断是否被反转
    if(x == y)
    {
        ones[cur] = a[x]; // a[]中存放的是序列
        return ;
    }
    build(ls, x, mid);
    build(rs, mid + 1, y);
    update(cur);
}
 
// 调用build建立线段树
build(1, 1, N);
 
 

2.线段树的修改:

// 下传lazy标记的pushdown函数void pushdown(int cur, int x, int y){    int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1;    if(to[cur] != -1)//已经被标记    {        to[ls] = to[rs] = to[cur];//传递到子节点        rev[ls] = rev[rs] = 0;//标记为未被反转        ones[ls] = to[cur] * (mid - x + 1);//计算左儿子的值        ones[rs] = to[cur] * (y - mid);//计算右儿子的值        to[cur] = -1;//父节点消除懒惰标记    }    if(rev[cur])//如果父节点已经被反转    {        rev[ls] ^= 1, rev[rs] ^= 1;//儿子节点也跟随反转        ones[ls] = mid - x + 1 - ones[ls];//因为节点值都为1或者0,那么便可以用mid-x+1表示全为1的情况,那么减去ones[ls]便可以得到反转以后的数据        ones[rs] = y - mid - ones[rs];//理由同上        rev[cur] = 0;//已经传递到儿子,把父节点置为未反转    }}// 将[s,t]区间内所有整数赋值成0或者1void change(int cur, int x, int y, int s, int t, int v){    int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1;    if(x >= s && y <= t)    {        ones[cur] = v * (y - x + 1);        to[cur] = v, rev[cur] = 0;        return ;    }    pushdown(cur, x, y);    if(mid >= s)//这里注意理解,如果所求区间在原有区间的中点左右分布,那么两个if可以同时执行        change(ls, x, mid, s, t, v);    if(mid + 1 <= t)        change(rs, mid + 1, y, s, t, v);    update(cur);}

3.线段树的反转:

// 将[s,t]区间内所有0变为1,所有1变为0void reverse(int cur, int x, int y, int s, int t){    int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1;    if(x >= s && y <= t)    {        ones[cur] = y - x + 1 - ones[cur];        rev[cur] ^= 1;        return ;    }    pushdown(cur, x, y);    if(mid >= s)        reverse(ls, x, mid, s, t);    if(mid + 1 <= t)        reverse(rs, mid + 1, y, s, t);    update(cur);}

4.线段树的查询:

// 查询区间[s,t]内1的个数void query(int cur, int x, int y, int s, int t, int &ans){    int mid = (x + y) >> 1, ls = cur << 1, rs = cur << 1 | 1;    if(x >= s && y <= t)    {        ans += ones[cur];        return ;    }    pushdown(cur, x, y);    if(mid >= s)        query(ls, x, mid, s, t, ans);    if(mid + 1 <= t)        query(rs, mid + 1, y, s, t, ans);}