CSP-S 模板题精讲 线段树:区间修改 区间查询 黑猫OJ #B337. 线段树1

【模板题目】

【题目考点】

线段树 延迟标记

本题要求维护区间和，实现区间修改、区间查询。可以使用树状数组或线段树完成该问题，本文仅介绍使用线段树的解法。

该题中已经给出了线段树建树的方法。本文主要介绍如何在线段树上进行区间修改与区间查询。

1. 延迟标记

原数值序列输入到数组，叫做序列。对序列建立线段树。区间修改操作为使序列区间中的元素都增加数值。区间查询为返回区间中元素的加和。考虑维护区间和的线段树数组应该如何变化。（1） 延迟标记如果线段树中结点表示的区间被区间完全覆盖，则可以考虑不去修改结点的子孙结点的值，而是直接在结点上增加延迟标记。延迟标记，也叫懒标记（Lazy Tag），是保存在线段树结点中的一个成员变量，记为tag。

structNode{int l, r;longlong val, tag;} tree[4*N];

如果结点p的标记tree[p].tag大于0，表示结点p所表示的区间[tree[p].l, tree[p].r]中所有元素都应该加上tag。当前结点p的值tree[p].val已更新，但结点p的子孙结点的值都未更新。设置addTag函数完成将结点所表示的区间中所有元素都增加，实际操作为在改变结点的标记tag，同时修改结点的值val。

voidaddTag(int i, longlong v){//在地址为i的结点表示的区间[tree[i].l, tree[i].r]中每个元素增加v    tree[i].tag += v;//增加标记    tree[i].val += (tree[i].r-tree[i].l+1)*v;//区间[l, r]共有r-l+1个元素，每个元素增加v，共增加(r-l+1)*v。}

（2） 标记下传如果需要访问线段树中当前结点的子结点，则需要保证子结点的值val是正确的。如果当前结点的标记tag不为0，则表示对当前结点p表示的区间存在一些修改操作，而这些修改操作并没有作用到结点p的子孙结点。我们需要根据结点p的标记对结点p的子结点进行修改，而后将结点p的标记归零，这样就可以保证结点p的子结点的值就是该结点所表示区间的加和。

标记下传(pushDown)：根据当前结点的标记tag更新该结点的子结点的标记tag与值val具体步骤为：

1. 如果当前结点标记为0，则返回。
2. 根据当前标记更新当前结点左右孩子的值，并为左右孩子增加标记。
3. 当前结点标记清零。

voidpushDown(int i)//地址为i的结点标记下传{if(tree[i].tag == 0)return;    addTag(2*i, tree[i].tag);    addTag(2*i+1, tree[i].tag);    tree[i].tag = 0;}

2. 区间修改

区间修改操作为使序列区间中的元素都增加数值。在线段树中，访问到地址为结点，考虑区间修改操作如何影响当前结点表示的区间对应线段树中各结点的值。

1. 如果当前结点表示的区间和区间不相交，则直接返回。
2. 如果当前结点表示的区间完全被区间覆盖时，只修改当前结点的标记和值，不再修改其子孙。
3. 否则当前结点的左右孩子表示的区间都可能与区间有交集。在修改子孙结点前，应该先进行标记下传pushDown操作，更新孩子结点的标记和值。而后对当前结点的左右孩子进行对区间的区间修改操作。
4. 当前结点左右子树的值更新结束后，再进行pushUp操作，根据左右孩子的值更新当前结点的值。

该操作与区间查询的时间复杂度相同，为。

voidupdate(int i, int l, int r, longlong v)//在结点地址为i的子树中，区间[l, r]中的所有元素增加v{if(tree[i].r < l || tree[i].l > r)return;if(l <= tree[i].l && tree[i].r <= r) {        addTag(i, v);return;    }    pushDown(i);//注意每到达一个顶点都要标记下传    update(2*i, l, r, v);    update(2*i+1, l, r, v);    pushUp(i);//根据孩子的值更新结点i的值}

3. 区间查询

要查询a序列给定区间中元素的加和，要做的是将区间划分为几个线段树中结点表示的区间，将这些区间的值加和。要在地址为i的结点表示的区间中，返回中元素的加和：

1. 判断当前结点表示的区间和是否有交集。如果没有交集则返回。
2. 如果当前结点表示的区间完全被区间包含，则返回当前结点的值。
3. 否则需要通过访问子结点来获取区间中元素的加和。访问子结点前需要先进行标记下传pushDown操作。而后分别在当前结点的两个子树中查询区间中元素的加和，将二者的加和返回。区间查询的时间复杂度为

//在地址为i的子树中，查询区间[l, r]中所有元素的加和longlongquery(int i, int l, int r){    if(tree[i].r < l || tree[i].l > r)return0;if(l <= tree[i].l && tree[i].r <= r)return tree[i].val;         pushDown(i);//如果要访问结点i的孩子，则标记下传return query(2*i, l, r)+query(2*i+1, l, r);}

注意：本题数值范围达到，与数值相关的变量都要设为long long类型。

【题解代码】

解法1：线段树

#include<bits/stdc++.h>usingnamespacestd;#define N 100005structNode{int l, r;longlong val, tag;} tree[4*N];longlong n, m, a[N];voidpushUp(int i){    tree[i].val = tree[2*i].val+tree[2*i+1].val;}voidaddTag(int i, longlong v)//结点i增加标记v {    tree[i].tag += v;    tree[i].val += (tree[i].r-tree[i].l+1)*v; }voidpushDown(int i)//标记下传 {if(tree[i].tag == 0)return;    addTag(2*i, tree[i].tag);    addTag(2*i+1, tree[i].tag);    tree[i].tag = 0;}voidbuild(int i, int l, int r)//建立线段树 {    tree[i].l = l, tree[i].r = r;if(l == r)    {        tree[i].val = a[l];return;    }int mid = l+r>>1;    build(2*i, l, mid);    build(2*i+1, mid+1, r);    pushUp(i);}voidupdate(int i, int l, int r, longlong v)//区间修改 每个元素增加v {if(tree[i].r < l || tree[i].l > r)return;if(l <= tree[i].l && tree[i].r <= r)return addTag(i, v);    pushDown(i);    update(2*i, l, r, v);    update(2*i+1, l, r, v);    pushUp(i);}longlongquery(int i, int l, int r)//区间查询[l, r]中的值 {if(tree[i].r < l || tree[i].l > r)return0;if(l <= tree[i].l && tree[i].r <= r)return tree[i].val;    pushDown(i);return query(2*i, l, r)+query(2*i+1, l, r);}intmain(){    ios::sync_with_stdio(false);cin.tie(nullptr);longlong op, x, y, k;cin >> n >> m;for(int i = 1; i <= n; ++i)cin >> a[i];    build(1, 1, n);for(int i = 1; i <= m; ++i)    {cin >> op;if(op == 1)        {cin >> x >> y >> k;            update(1, x, y, k);        }else        {cin >> x >> y;cout << query(1, x, y) << '\n';         }    }return 0;}