线段树

线段树

题目链接：https://www.luogu.com.cn/problem/P3372

题目：

题目描述 如题，已知一个数列，你需要进行下面两种操作：

将某区间每一个数加上 kk。
求出某区间每一个数的和。

输入格式

第一行包含两个整数 n, mn,m，分别表示该数列数字的个数和操作的总个数。

第二行包含 nn 个用空格分隔的整数，其中第 ii 个数字表示数列第 ii 项的初始值。

接下来 mm 行每行包含 33 或 44 个整数，表示一个操作，具体如下：

1 x y k：将区间 [x, y][x,y] 内每个数加上 kk。
2 x y：输出区间 [x, y][x,y] 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

输出

11
8
20

参考博客：https://blog.csdn.net/cowgoodsheep/article/details/123358880

参考博客：https://zhuanlan.zhihu.com/p/106118909

解题思路：

如果每次都仅仅查询每段的和的话，我们可以累加段的和，然后用大段和减小段得到中间一段的和。

用raw_data[i]表示原数据的第i个

用data[i]表示data[0]-data[i]的和，可知段s-e的和为data[e]-data[s-1]。

但是本题中还需要修改某一段，如果暴力修改每一个数据太慢了，期望能够有一个能批量修改的方法，比如一个节点表示了s-e的这段数据的和，那么假如要给这一段再加d，那么我们只需要修改这个节点即可，但是不可能给每一段都搞一个这样的节点，所以我们可以采用二叉树，用二分的思想，这样任何一段都能被二叉树中的点分担。

可这我们拿到初始数据后需要建立二叉树，build

更新二叉树需要update

查询二叉树需要query

build：

数组二叉树如果把1当作根，那么每个节点的左右孩子比较好找，root2和root2+1，所以我们从1开始建树。

假设有n个数据，1-n，为了查询更快，我们需要建立一颗平衡树。

设根为root，可知root这个位置要存1-n的数据之和，为了平衡树，所以每次左右子树各给一半，左子树的位置是root2，这位置存1-n/2的和，右子树的位置是root2+1,存n/2+1-n的数据之和。不断递归直到只剩一个数据不用再分左右子树了，就把数据直接给这个节点。

update：

假设要给l到r加上d，那么我们从根节点开始分配任务，把任务丢给左右孩子，左右孩子更新好后，更新当前root的值。

如果一个孩子管理的一段全部属于要更改的那一大段，那么就只在在这个节点这里打个懒标记mark[root]+=d，并且把当前节点的值直接更新一下即可tree[root]+=d*(cr-cl+1),这里的cl和cr表示当前节点管理的最左边和最右边的序号，这样就不用每次都遍历到底。如果需要访问孩子，那么把当前节点的懒标记mark[root]给分发给子节点即可(push_down)。

query：

假设要查询l到r的和，那么还是从根节点分发任务，让左右孩子解决，然后返回左右孩子结果的和。

如果有孩子管理的一段属于l到r，那么直接返回当前节点的值即可。

如果当前节点有懒标记，那么同update一样先push_down一下，把当前节点的懒标记分发给孩子即可。

push_down:

分发root的懒标记时要注意，一个节点的懒标记动的时候一定要把动的量及时更新到其节点上，因为懒标记可以叠加，如果不及时更新，到时候就分不清懒标记中哪部分已经更新了，哪部分没更新了。

不及时更新的错误举例：

比如一个节点root1，第一次让root1加1，然后询问root1这个节点的结果，这下你加了一下mark这个懒标记，但是由于可能要push_down给孩子节点，你不能清除该懒标记

下次又更新一次root1，让root1加2，再询问root1，这次你怎么知道mark这个懒标记1那部分已经更新过了，而这次的2没有呢？混到一起了。

所以每次动一个节点的mark懒标记时，都要立即更新它的值

// SegmentTree.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <stdio.h>
#include <string.h>
#include <queue>

using namespace std;
using ll = long long;

const int MAXN = 1e5 + 5;
ll tree[MAXN*3], mark[MAXN*3], n, m, raw_data[MAXN];

void build(int root, int cl, int cr)
{
    // 以root为根节点，处理原始数据的cl到cr这部分的数据
    // 如果cl==cr说明就一个数，那么就直接放在root这里就好
    // 否则以root为根节点，左右孩子各处理一半
    if (cl == cr)
    {
        tree[root] = raw_data[cl];
        return;
    }
    int mid = (cl + cr) /2;
    int left_child = root * 2, right_child = root * 2 + 1;
    build(left_child, cl, mid);
    build(right_child, mid + 1, cr);
    // 左右孩子的树建立好了之后，更新一下当前root的结果，这里是求和，也可以是其他运算
    tree[root] = tree[left_child] + tree[right_child];
}

void push_down(int root, int cl, int cr)
{
    // push_down的作用就是把当前的懒标记，更新给孩子，因为一定是有人调用了孩子，这个懒标记给了孩子之后记得把标记去除
    int mid = (cl + cr) / 2;
    int left_child = root * 2, right_child = root * 2 + 1;
    mark[left_child] += mark[root];
    mark[right_child] += mark[root];
    // 懒标记有可能会累积，如果不及时把数值加到tree上，到时候就不知道有多少标记已经被加过了，有多少没被加过，所以这里及时把这次的数值累加上来
    // 不及时更新的错误举例：
    //   比如一个节点root1，第一次让root1加1，然后询问root1这个节点的结果，这下你加了一下mark这个懒标记，但是由于可能要push_down给孩子节点，你不能清除该懒标记
    //   下次又更新一次root1，让root1加2，再询问root1，这次你怎么知道mark这个懒标记1那部分已经更新过了，而这次的2没有呢？混到一起了。
    //   所以每次动一个节点的mark懒标记时，都要立即更新它的值
    tree[left_child] += (mark[root] * (mid - cl + 1));
    tree[right_child] += (mark[root] * (cr - mid));
    mark[root] = 0;
}

void update(int root, int cl, int cr, int l, int r, int d)
{
    // 更新区域与当前区域没有交集
    if (r < cl || cr < l)return;
    // 更新区域包含当前区域
    if (l <= cl && cr <= r)
    {
        mark[root] += d;
        tree[root] += d*(cr - cl + 1);
        if (cl == cr)mark[root] = 0;
        return;
    }
    // 更新区域包含当前区域的一部分
    int mid = (cl + cr) / 2;
    int left_child = root * 2, right_child = root * 2 + 1;
    push_down(root, cl, cr);
    update(root * 2, cl, mid, l, r, d);
    update(root * 2+1, mid+1, cr, l, r, d);
    tree[root] = tree[left_child] + tree[right_child];
}

ll query(int root, int cl, int cr, int l, int r)
{
    // 更新区域与当前区域没有交集
    if (r < cl || cr < l)return 0;
    // 更新区域包含当前区域
    if (l <= cl && cr <= r)return tree[root];
    int mid = (cl + cr) / 2;
    int left_child = root * 2, right_child = root * 2 + 1;
    push_down(root, cl, cr);
    ll ans = query(left_child, cl, mid, l, r)+query(right_child, mid+1, cr, l, r);
    return ans;
}

void PrintTree()
{
    queue<int> q;
    q.push(1);
    printf("tree start\n");
    int max_no = 9;

    while (q.size())
    {
        int layer_size = q.size();
        for (int i = 0; i != layer_size; i++)
        {
            int t = q.front();
            q.pop();
            int left_child = t * 2, right_child = t * 2 + 1;
            if (left_child <= max_no)q.push(left_child);
            if (right_child <= max_no)q.push(right_child);
            printf("%d ", tree[t]);
        }
        printf("\n");
    }
    printf("tree end\n");
}

int main()
{
    freopen("D:/c++/dev-data/in.txt", "r", stdin);
    int o, l, r, d;
    while(~scanf("%d %d", &n, &m))
    {
        memset(tree, 0, sizeof(tree));
        memset(mark, 0, sizeof(mark));
        memset(raw_data, 0, sizeof(raw_data));
        for (int i = 1; i <= n; ++i)
            scanf("%d", &raw_data[i]);
        build(1, 1, n);
        //PrintTree();
        while (m--)
        {
            scanf("%d %d %d", &o, &l, &r);
            if (o == 1)
            {
                scanf("%d", &d);
                update(1, 1, n, l, r, d);
            }
            else
            {
                printf("%lld\n", query(1, 1, n, l, r));
            }
            //PrintTree();
        }
    }
    return 0;
}

Etherwave's Blog Hi~ o(*￣▽￣*)ブ

文章目录