线段树（tag标记后效性）

线段树模板

题意概括

实现一棵线段树，有如下操作

1 l r 询问区间[l,r]内的元素和
2 l r 询问区间[l,r]内的元素的平方和
3 l r x 将区间[l,r]内的每一个元素都乘上x
4 l r x 将区间[l,r]内的每一个元素都加上x

注意

我们可以用面向对象的方法来构建线段树
这道题有两个tag: * 和 +, 对于lazy标记我们可以单独用函数封装
init_lazy(), cal_lazy(), union_lazy(), pushdown()

init_lazy()

把*的标记置为1， +的标记置为0

void init_lazy(int root)
{
    tree[root].lazy[0] = 1;
    tree[root].lazy[1] = 0;
}

union_lazy()

其实就是数学计算
当把父节点的标记下去的时候，子节点+标记也被影响了
作用是把父节点的lazy标记传下去

void union_lazy(int fa, int ch)
{
    lli tmp[2];
    tmp[0] = tree[fa].lazy[0] * tree[ch].lazy[0];
    tmp[1] = tree[fa].lazy[0] * tree[ch].lazy[1] + tree[fa].lazy[1];
    tree[ch].lazy[0] = tmp[0];
    tree[ch].lazy[1] = tmp[1];
}

cal_lazy()

这个也是数学计算
作用是pushdown的时候把结果算出来

// 两个sum, 一个计算平方和， 一个计算正常和
void cal_lazy(int root)
{
    tree[root].sum[0] = tree[root].lazy[0] * tree[root].sum[0] + tree[root].lazy[1] * (tree[root].right - tree[root].left + 1);

    tree[root].sum[1] = tree[root].lazy[0] * tree[root].lazy[0] * tree[root].sum[1] + tree[root].lazy[1] * tree[root].lazy[1] * 
                        (tree[root].right - tree[root].left + 1) + tree[root].lazy[0] * tree[root].lazy[1] * 2 * tree[root].sum[0];
    return;
}

pushdown()

作用是把Lazy标记的影响传下去

void pushdown(int root)
{
    if (tree[root].sum[0] != 1 || tree[root].sum[1] != 0)
    {
        cal_lazy(root);
        if (tree[root].left != tree[root].right)
        {
            int ch = root << 1;
            union_lazy(root, ch);
            union_lazy(root, ch + 1);
        }
        init_lazy(root);
    }
}

完整代码

// 用面向对象的思想看懒标记
// 为懒标记设计这么几个函数
// pushdown()
// cal_lazy()
// tag_union()
#include <bits/stdc++.h>
using lli = long long;
const int inf = 1e6;
int nums[inf] = {0};

struct tnode
{
    // sum[0]存的是*， sum[1]存的是+
    int left, right;
    lli sum[2], lazy[2];
};


struct SegmentTree
{
    tnode tree[4 *inf];
    int mp[inf];

    void init_lazy(int root)
    {
        tree[root].lazy[0] = 1;
        tree[root].lazy[1] = 0;
    }

    void union_lazy(int fa, int ch)
    {
        lli tmp[2];
        tmp[0] = tree[fa].lazy[0] * tree[ch].lazy[0];
        tmp[1] = tree[fa].lazy[0] * tree[ch].lazy[1] + tree[fa].lazy[1];
        tree[ch].lazy[0] = tmp[0];
        tree[ch].lazy[1] = tmp[1];
    }
    // 两个sum, 一个计算平方和， 一个计算正常和
    void cal_lazy(int root)
    {
        tree[root].sum[0] = tree[root].lazy[0] * tree[root].sum[0] + tree[root].lazy[1] * (tree[root].right - tree[root].left + 1);

        tree[root].sum[1] = tree[root].lazy[0] * tree[root].lazy[0] * tree[root].sum[1] + tree[root].lazy[1] * tree[root].lazy[1] * 
                            (tree[root].right - tree[root].left + 1) + tree[root].lazy[0] * tree[root].lazy[1] * 2 * tree[root].sum[0];
        return;
    }

    void pushdown(int root)
    {
        if (tree[root].sum[0] != 1 || tree[root].sum[1] != 0)
        {
            cal_lazy(root);
            if (tree[root].left != tree[root].right)
            {
                int ch = root << 1;
                union_lazy(root, ch);
                union_lazy(root, ch + 1);
            }
            init_lazy(root);
        }
    }

    void update(int root)
    {
        int ch = root << 1;
        pushdown(ch);
        pushdown(ch + 1);
        tree[root].sum[0] = tree[ch].sum[0] + tree[ch + 1].sum[0];
        tree[root].sum[1] = tree[ch].sum[1] + tree[ch + 1].sum[1];
    }

    void build(int root, int left, int right)
    {
        tree[root].left = left;
        tree[root].right = right;
        if (left == right)
        {
            tree[root].sum[0] = nums[left];
        }
        int ch = root << 1;
        int mid = (left + right) / 2;
        build(ch, left, mid);
        build(ch + 1, mid + 1, right);
    }

    void change(int root, int left, int right, lli delta, int op)
    {
        pushdown(root);
        if (left <= tree[root].left && tree[root].right <= right)
        {
            tree[root].lazy[op] = delta;
            return;
        }
        int mid = (tree[root].left + tree[root].right) << 1;
        int ch = root << 1;
        if (right <= mid)
        {
            change(ch, left, right, delta, op);
        }
        else if (left > mid)
        {
            change(ch + 1, left, right, delta, op);
        }
        else
        {
            change(ch, left, mid, delta, op);
            change(ch + 1, mid + 1, right, delta, op);
        }
        update(root);
    }

    lli calc(int root, int left, int right, int op)
    {
        pushdown(root);
        if (left <= tree[root].left && tree[root].right <= right)
        {
            return tree[root].sum[op];
        }
        int mid = (tree[root].left + tree[root].right) << 1;
        int ch = root << 1;
        if (right <= mid)
        {
            return calc(ch, left, right, op);
        }
        else if (left > mid)
        {
            return calc(ch + 1, left, right, op);
        }
        else
        {
            return calc(ch, left, mid, op) + calc(ch + 1, mid + 1, right, op);
        }
    }
};

int main()
{

    return 0;
}