线段树QWQ

一直没碰过线段树，个人认为好长好难，不过这几天做题遇到了裸的线段树的题，TAT。

线段树我理解就是把二叉树的左右节点现在分别看成是两个区间。

那么现在这两个区间的端点怎么存放？怎么能够把这个区间里的数（一般指的就是在这个区间的数值的和）存放起来呢？

比较传统化的是用一个结构体来存放。比如：

struct node

{

    int l, r;  // l,r分别是左右端点

    int w;     // 用来存放这个区间的值（和）

};

这样就可以解决了数值的存放问题了。

学习建立二叉树的时候是用指针、结构体来建立的，依靠指针来找子节点或者根节点，当然在线段树中依然可以那么建立，不过

在使用时可能会因为指针的特点，RE之类的错误经常出现，于是就是就有人想到用结构体类型数组来模拟建立。

这个结构体需要开多么大才合适呢？

一般需要开4倍空间才可以。（当时自我感觉认为3倍就够了，但是RE了一次，可以在纸上手动画一下，帮助理解）

线段树一般就是来解决比较直观的问题（当然也有好多神级题目来考你的线段树,这里暂时忽略一下），比如给你一个N长度的一

组数，再给你L、R。这样就可以问你：任意L~R之间的数的和（这就是所谓区间查询，当L==R时，就变成了单点查询）。

如果仅仅是查询那么前缀和就可以做了，如果数据N不大，直接暴力就好了。

现在再加一个操作，给你L、R、X，每次在L~R区间上加上X（这就是区间修改，当L==R时，就是单点修改），这个操作后再查

询，这两个操作的次数非常多，一般都会TLE了。

这样的问题就可以用线段树来解决了。

首先是建一颗线段树：

void BuildSegmentTree(int k, int l, int r)

{

    tree[k].l = l;            // 存放左右端点

    tree[k].r = r;

    if(l == r)               // 如果是l==r时，就是到了线段树的最下层，也就是叶子，存放数本身的值。

    {

        scanf("%lld", &tree[k].w);

        return ;             // ！！！

    }

    int m = (tree[k].l + tree[k].r) >> 1;              //  m = (tree[k].l + tree[k].r) / 2;

    BuildSegmentTree(k << 1, l, m);

    BuildSegmentTree(k << 1 | 1, m + 1, r);

    tree[k].w = tree[k << 1].w + tree[k << 1 | 1].w;    // tree[k << 1 | 1].w 相当于 tree[k * 2 + 1].w

}

建树的过程比较简单，就是递归建树就可以了。

<以下操作的英文名字纯属为了避免混淆了，根据自己喜欢命名即可>

1、单点修改（Single point modification）

void Single_Point_Modification(int k, int x, int y)  // x是待修改的点，y是添加的值

{

    if(tree[k].l == tree[k].r)                      // 如果是叶子，也就找到了单个点

    {

        tree[k].w += y;

        return ;

    }

    int m = (tree[k].l + tree[k].r) >> 1;

    if(x <= m) Single_Point_Modification(k << 1,x, y);  //如果待修改值x小于中间值，递归左边

    else Single_Point_Modification(k << 1 | 1, x, y);   //如果待修改值x小于中间值，递归左边

    tree[k].w = tree[k << 1].w + tree[k << 1 | 1]. w;   //别忘了因为修改这个值，所以需要更新它的上一层的值

}

2、单点查询（Single point query）

void Single_Point_Query(int k, int x)         // 单点查询比较好理解，如果查到了直接返回就好了，所以函数可以写成int类型

{

    if(tree[k].l == tree[k].r)                // x为需要查询的点

    {

        ans = tree[k].w;

        return ;

    }

    int m = (tree[k].l + tree[k].r) >> 1;

    if(x <= m) Single_Point_Query(k << 1, x);

    else Single_Point_Query(k << 1 | 1, x);

}

3、区间查询（Interval query）

void Interval_Query(int k, int x, int y)         //查询区间x~y

{

    if(tree[k].l >= x && tree[k].r <= y)        // 如果查询的区间在这个范围内，直接加上

    {

        ans += tree[k].w;

        return ;

    }

    int m = (tree[k].l + tree[k].r) / 2;        // 继续递归查询

    if(x <= m) Interval_Query(k << 1, x, y);

    if(y > m) Interval_Query(k << 1 | 1, x, y);

}

4、区间修改（Interval modification）

在区间修改时会遇到一些问题，如果每次修改都是查询到叶子所在的点来修改，再返回到上一层，依次完成更新，如果是这种操作理论上时间复杂度就是比较高了，如果是查询、修改、查询……这样可能就要QAQ了。可以换一种想法，只有需要查询到修改过的这个区间时，我们才把修改过的这个区间的值算一下，如果没有查询到这个区间，那么这个修改的值就一直存在上一层不动（相当于它的父节点就可以了，如果查询到了，根据这个区间的数的个数把每个数都加上就可以，然后把在父节点的这个标记更新清零），因为用到才会更新的原因吧，所以这个标记就被称作是懒标记了。

如果需要进行区间修改那么结构体中就要多一个变量，来存放需要的那个懒标记。

struct node

{

    int l, r;  // l,r分别是左右端点

    int w;     // 用来存放这个区间的值（和）

    int f;     // 懒标记

};

现在知道了这种思想，那么如果实现的话，首先是这个标记怎么把它传下去呢？

只要是修改的区间包括了k这个点，就需要把懒标记下传下去，然后更新w值，再把标记清零。

void down(int k)

{

    tree[k << 1].f += tree[k].f;        // 子节点都要加上标记

    tree[k << 1 | 1].f += tree[k].f;

    tree[k << 1]. w += tree[k].f * (tree[k << 1].r - tree[k << 1].l + 1);    // 数值更新

    tree[k << 1 |1].w += tree[k].f * (tree[k << 1| 1].r - tree[k << 1| 1].l + 1);

    tree[k].f = 0;                     // “父节点”（懒标记）清零

}

区间修改：

void Interval_modification(int k, int x, int y,int z)  // [x,y]区间上每个值都加上z

{

    if(tree[k].l >= x && tree[k].r <= y)  //如果全部在这个区间内，那么这个区间的总个数*z的值加在父节点上即可

    {

        tree[k].w += (tree[k].r - tree[k].l + 1) * z;

        tree[k].f += z;                                 // 把标记存在这个地方，如果还可以继续往下访问，利用down来解决

        return;

    }

    if(tree[k].f) down(k);                           //懒标记下传。

    int m = (tree[k].l + tree[k].r) >> 1;

    if(x <= m) Interval_modification(k << 1, x, y, z);

    if(y > m) Interval_modification(k << 1 | 1, x, y, z);

    tree[k].w = tree[k << 1].w + tree[k << 1 | 1].w;     // 存放更新后的值

}

当然不喜欢这么多函数，就把懒标记下传写到这里面去就可以了。

合并以后：

void Interval_modification(int k, int x, int y,int z)  // [x,y]区间上每个值都加上z

{

    if(tree[k].l >= x && tree[k].r <= y)// 如果全部在这个区间内，那么这个区间的总个数*z的值加在父节点上即可

    {

        tree[k].w += (tree[k].r - tree[k].l + 1) * z;

        tree[k].f += z;                                 // 把标记存在这个地方，如果还可以继续往下访问，利用down来解决

        return;

    }

    if(tree[k].f)     //懒标记下传。

    {

        tree[k << 1].f += tree[k].f;        // 子节点都要加上标记

        tree[k << 1 | 1].f += tree[k].f;

        tree[k << 1]. w += tree[k].f * (tree[k << 1].r - tree[k << 1].l + 1);    // 数值更新

        tree[k << 1 |1].w += tree[k].f * (tree[k << 1| 1].r - tree[k << 1| 1].l + 1);

        tree[k].f = 0;                     // “父节点”（懒标记）清零

    }

    int m = (tree[k].l + tree[k].r) >> 1;

    if(x <= m) Interval_modification(k << 1, x, y, z);

    if(y > m) Interval_modification(k << 1 | 1, x, y, z);

    tree[k].w = tree[k << 1].w + tree[k << 1 | 1].w;     // 存放更新后的值

}

加上了懒标记之后，相应的单点查询、区间修改都要加上判断懒标记的条件，即：

if(tree[k].f) down(k);

以上就是线段树的基本操作了，其实如果想加深理解除了手动计算计算，做几道可以更快的理解。

线段树多做做就好啦，QWQ。

巴特西

线段树QWQ

最新文章

热门文章