洛谷 P3372 【模板】线段树 1
【题目链接】洛谷 P3372 【模板】线段树 1
【题目考点】
1. 线段树
2. 树状数组
【解题思路】
本题要求维护区间和，实现区间修改、区间查询。
可以利用树状数组或线段树完成该问题，本文仅先容利用线段树的解法。
解法1：线段树
线段树的基础概念及性质见：洛谷 P3374 【模板】树状数组 1（线段树解法）
上题中已经给出了线段树建树的方法。本文主要先容如安在线段树上进行区间修改与区间查询。
1. 延迟标记
原数值序列输入到a数组，叫做a序列。对a序列创建线段树。
区间修改操纵为使a序列区间 [ l , r ] 中的元素都增加数值v。区间查询为返回区间 [ l , r ] 中元素的加和。思量维护区间和的线段树数组应该如何厘革。
（1） 延迟标记
假如线段树中结点p表示的区间被区间 [ l , r ] 完全覆盖，则可以思量不去修改结点p的子孙结点的值，而是直接在结点p上增加延迟标记。
延迟标记，也叫懒标记（Lazy Tag），是生存在线段树结点中的一个成员变量，记为tag。
struct Node
{
int l, r;
long long val, tag;
} tree;
假如结点p的标记tree.tag大于0，表示结点p所表示的区间.l, tree.r]中所有元素都应该加上tag。当前结点p的值tree.val已更新，但结点p的子孙结点的值都未更新。
设置addTag函数完成将结点i所表示的区间中所有元素都增加v，现实操纵为在改变结点i的标记tag，同时修改结点i的值val。
void addTag(int i, long long v)
{//在地址为i的结点表示的区间.l, tree.r]中每个元素增加v
tree.tag += v;//增加标记
tree.val += (tree.r-tree.l+1)*v;//区间共有r-l+1个元素，每个元素增加v，共增加(r-l+1)*v。
}
（2） 标记下传
假如需要访问线段树中当前结点的子结点，则需要保证子结点的值val是正确的。
假如当前结点p的标记tag不为0，则表示对当前结点p表示的区间存在一些修改操纵，而这些修改操纵并没有作用到结点p的子孙结点。我们需要根据结点p的标记对结点p的子结点进行修改，而后将结点p的标记归零，这样就可以保证结点p的子结点的值就是该结点所表示区间的加和。
标记下传(pushDown)：根据当前结点的标记tag更新该结点的子结点的标记tag与值val
具体步骤为：
[*]假如当前结点标记为0，则返回。
[*]根据当前标记更新当前结点左右孩子的值，并为左右孩子增加标记。
[*]当前结点标记清零。
void pushDown(int i)//地址为i的结点标记下传
{
if(tree.tag == 0)
return;
addTag(2*i, tree.tag);
addTag(2*i+1, tree.tag);
tree.tag = 0;
}
2. 区间修改
区间修改操纵为使a序列区间 [ l , r ] 中的元素都增加数值v。
在线段树中，访问到地址为i结点，思量区间修改操纵如何影响当前结点表示的区间对应线段树中各结点的值。
[*]假如当前结点表示的区间和区间 [ l , r ] 不相交，则直接返回。
[*]假如当前结点表示的区间完全被区间 [ l , r ] 覆盖时，只修改当前结点的标记和值，不再修改其子孙。
[*]否则当前结点的左右孩子表示的区间都可能与区间 [ l , r ] 有交集。在修改子孙结点前，应该先进行标记下传pushDown操纵，更新孩子结点的标记和值。而后对当前结点的左右孩子进行对区间 [ l , r ] 的区间修改操纵。
[*]当前结点左右子树的值更新竣事后，再进行pushUp操纵，根据左右孩子的值更新当前结点的值。
该操纵与区间查询的时间复杂度相同，为 O ( log n ) O(\log n) O(logn)。
void update(int i, int l, int r, long long v)//在结点地址为i的子树中，区间中的所有元素增加v
{
if(tree.r < l || tree.l > r)
return;
if(l <= tree.l && tree.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序列给定区间 [ l , r ] 中元素的加和，要做的是将 [ l , r ] 区间划分为几个线段树中结点表示的区间，将这些区间的值加和。
要在地址为i的结点表示的区间中，返回 [ l , r ] 中元素的加和：
[*]判断当前结点表示的区间和 [ l , r ] 是否有交集。假如没有交集则返回。
[*]假如当前结点表示的区间完全被区间 [ l , r ] 包罗，则返回当前结点的值。
[*]否则需要通过访问子结点来获取区间 [ l , r ] 中元素的加和。
访问子结点前需要先进行标记下传pushDown操纵。
而后分别在当前结点的两个子树中查询区间 [ l , r ] 中元素的加和，将二者的加和返回。
区间查询的时间复杂度为 O ( log n ) O(\log n) O(logn)
(证实见洛谷 P3374 【模板】树状数组 1（线段树解法）)
//在地址为i的子树中，查询区间中所有元素的加和
long long query(int i, int l, int r)
{ if(tree.r < l || tree.l > r)
return 0;
if(l <= tree.l && tree.r <= r)
return tree.val;
pushDown(i);//如果要访问结点i的孩子，则标记下传
return query(2*i, l, r)+query(2*i+1, l, r);
}
注意：本题数值范围达到 10 18 10^{18} 1018，与数值相干的变量都要设为long long类型。
解法2：树状数组
本解法不如利用线段树更加直观，建议读者掌握上述线段树解法。树状数组解法仅作为参考。
原数组为数组a。对a数组的差分数组d建树状数组。
假如对原数组进行区间修改，即对a序列区间 [ l , r ] 中每个元素增加数值v，在差分数组d数组上的操纵为 d l = d l + v , d r + 1 = d r + 1 − v d_l =d_l+ v, d_{r+1} =d_{r+1}-v dl=dl+v,dr+1=dr+1−v。
进行区间查询，求a序列 [ l , r ] 中所有元素的和，可以借助a序列的前缀和求出。
记 a a a序列的前缀和为 s s s，则a序列区间 [ l , r ] 中所有元素的和为 s r − s l − 1 s_r-s_{l-1} sr−sl−1。
已知 s i = ∑ x = 1 i a x s_i = \sum\limits_{x=1}^ia_x si=x=1∑iax， a i = ∑ x = 1 i d x a_i = \sum\limits_{x=1}^id_x ai=x=1∑idx
所以
s i = ∑ x = 1 i ∑ y = 1 x d y s_i = \sum\limits_{x=1}^i\sum\limits_{y=1}^xd_y si=x=1∑iy=1∑xdy
= ∑ x = 1 i ( ∑ y = 1 i d y − ∑ y = x + 1 i d y ) + ( ∑ y = 1 i d y − ∑ y = 0 + 1 i d y ) = \sum\limits_{x=1}^i(\sum\limits_{y=1}^id_y-\sum\limits_{y=x+1}^id_y)+(\sum\limits_{y=1}^id_y-\sum\limits_{y=0+1}^id_y) =x=1∑i(y=1∑idy−y=x+1∑idy)+(y=1∑idy−y=0+1∑idy)
= ∑ x = 0 i ( ∑ y = 1 i d y − ∑ y = x + 1 i d y ) = \sum\limits_{x=0}^i(\sum\limits_{y=1}^id_y-\sum\limits_{y=x+1}^id_y) =x=0∑i(y=1∑idy−y=x+1∑idy)
= ∑ x = 0 i ∑ y = 1 i d y − ∑ x = 0 i ∑ y = x + 1 i d y = \sum\limits_{x=0}^i\sum\limits_{y=1}^id_y-\sum\limits_{x=0}^i\sum\limits_{y=x+1}^id_y =x=0∑iy=1∑idy−x=0∑iy=x+1∑idy
= ( i + 1 ) ∑ y = 1 i d y − ∑ x = 0 i ∑ y = x + 1 i d y = (i+1)\sum\limits_{y=1}^id_y-\sum\limits_{x=0}^i\sum\limits_{y=x+1}^id_y =(i+1)y=1∑idy−x=0∑iy=x+1∑idy
∑ x = 0 i ∑ y = x + 1 i d y \sum\limits_{x=0}^i\sum\limits_{y=x+1}^id_y x=0∑iy=x+1∑idy
= ∑ y = 1 i d y + ∑ y = 2 i d y + . . . + ∑ y = i i d y =\sum\limits_{y=1}^id_y+\sum\limits_{y=2}^id_y+...+\sum\limits_{y=i}^id_y =y=1∑idy+y=2∑idy+...+y=i∑idy
= 1 d 1 + 2 d 2 + . . . + i d i = ∑ y = 1 i y ⋅ d y =1d_1+2d_2+...+id_i = \sum\limits_{y=1}^iy\cdot d_y =1d1+2d2+...+idi=y=1∑iy⋅dy
因此 s i = ( i + 1 ) ∑ y = 1 i d y − ∑ y = 1 i y ⋅ d y s_i = (i+1)\sum\limits_{y=1}^id_y-\sum\limits_{y=1}^iy\cdot d_y si=(i+1)y=1∑idy−y=1∑iy⋅dy
假想存在f序列， f i = i ⋅ d i f_i = i\cdot d_i fi=i⋅di
设两个树状数组 t 1 , t 2 t_1, t_2 t1,t2，分别维护 d d d序列和 f f f序列的区间和。
进行单点修改时，假如 d i = d i + v d_i=d_i+v di=di+v，那么 f i = i ⋅ ( d i + v ) = f i + i ⋅ v f_i=i\cdot(d_i+v)=f_i+i\cdot v fi=i⋅(di+v)=fi+i⋅v。利用树状数组单点修改操纵完成上述修改，时间复杂度为 O ( log n ) O(\log n) O(logn)。
进行区间查询，求 s i s_i si，分别求出 d d d序列前i项的和 s d s_d sd，与 f f f序列前i项的和 s f s_f sf，而后 s i = ( i + 1 ) s d − s f s_i=(i+1)s_d-s_f si=(i+1)sd−sf，时间复杂度为 O ( log n ) O(\log n) O(logn)
【题解代码】
解法1：线段树
#include<bits/stdc++.h>
using namespace std;
#define N 100005
struct Node
{
int l, r;
long long val, tag;
} tree;
long long n, m, a;
void pushUp(int i)
{
tree.val = tree.val+tree.val;
}
void addTag(int i, long long v)//结点i增加标记v
{
tree.tag += v;
tree.val += (tree.r-tree.l+1)*v;
}
void pushDown(int i)//标记下传
{
if(tree.tag == 0)
return;
addTag(2*i, tree.tag);
addTag(2*i+1, tree.tag);
tree.tag = 0;
}
void build(int i, int l, int r)//建立线段树
{
tree.l = l, tree.r = r;
if(l == r)
{
tree.val = a;
return;
}
int mid = l+r>>1;
build(2*i, l, mid);
build(2*i+1, mid+1, r);
pushUp(i);
}
void update(int i, int l, int r, long long v)//区间修改 每个元素增加v
{
if(tree.r < l || tree.l > r)
return;
if(l <= tree.l && tree.r <= r)
return addTag(i, v);
pushDown(i);
update(2*i, l, r, v);
update(2*i+1, l, r, v);
pushUp(i);
}
long long query(int i, int l, int r)//区间查询中的值
{
if(tree.r < l || tree.l > r)
return 0;
if(l <= tree.l && tree.r <= r)
return tree.val;
pushDown(i);
return query(2*i, l, r)+query(2*i+1, l, r);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long op, x, y, k;
cin >> n >> m;
for(int i = 1; i <= n; ++i)
cin >> a;
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;
}
解法2：树状数组
#include<bits/stdc++.h>
using namespace std;
#define N 100005
long long n, m, t1, t2;//t1：差分数组d的树状数组 t2：i*d的树状数组
int lowbit(int x)
{
return x & -x;
}
void update(int i, long longv)//对c1、c2的单点修改
{
for(int x = i; x <= n; x += lowbit(x))
t1 += v, t2 += i*v;
}
void rangeUpdate(int l, int r, long longv)//对a的区间修改为对d的两个单点修改
{
update(l, v);
update(r+1, -v);
}
long longsum(int n)//a的前n个元素的加和
{
long long sd = 0, sf = 0;
for(int x = n; x > 0; x -= lowbit(x))
sd += t1, sf += t2;
return (n+1)*sd-sf;
}
long long query(int l, int r)
{
return sum(r)-sum(l-1);
}
int main()
{
long long a, op, x, y, k;
cin >> n >> m;
for(int i = 1; i <= n; ++i)
{
cin >> a;
rangeUpdate(i, i, a);
}
for(int i = 1; i <= m; ++i)
{
cin >> op;
if(op == 1)
{
cin >> x >> y >> k;
rangeUpdate(x, y, k);
}
else
{
cin >> x >> y;
cout << query(x, y) << endl;
}
}
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]