合肥外贸网站建设,垫江集团网站建设,wordpress特别卡 iis,wordpress调取指定分类下的文章【题目链接】
洛谷 P3372 【模板】线段树 1
【题目考点】
1. 线段树
2. 树状数组
【解题思路】
本题要求维护区间和#xff0c;实现区间修改、区间查询。 可以使用树状数组或线段树完成该问题#xff0c;本文仅介绍使用线段树的解法。
解法1#xff1a;线段树
线段树…【题目链接】
洛谷 P3372 【模板】线段树 1
【题目考点】
1. 线段树
2. 树状数组
【解题思路】
本题要求维护区间和实现区间修改、区间查询。 可以使用树状数组或线段树完成该问题本文仅介绍使用线段树的解法。
解法1线段树
线段树的基础概念及性质见洛谷 P3374 【模板】树状数组 1线段树解法
上题中已经给出了线段树建树的方法。本文主要介绍如何在线段树上进行区间修改与区间查询。
1. 延迟标记
原数值序列输入到a数组叫做a序列。对a序列建立线段树。 区间修改操作为使a序列区间 [ l , r ] [l, r] [l,r]中的元素都增加数值v。区间查询为返回区间 [ l , r ] [l, r] [l,r]中元素的加和。考虑维护区间和的线段树数组应该如何变化。 1 延迟标记 如果线段树中结点p表示的区间被区间 [ l , r ] [l,r] [l,r]完全覆盖则可以考虑不去修改结点p的子孙结点的值而是直接在结点p上增加延迟标记。 延迟标记也叫懒标记Lazy Tag是保存在线段树结点中的一个成员变量记为tag。
struct Node
{int l, r;long long val, tag;
} tree[4*N];如果结点p的标记tree[p].tag大于0表示结点p所表示的区间[tree[p].l, tree[p].r]中所有元素都应该加上tag。当前结点p的值tree[p].val已更新但结点p的子孙结点的值都未更新。 设置addTag函数完成将结点i所表示的区间中所有元素都增加v实际操作为在改变结点i的标记tag同时修改结点i的值val。
void addTag(int i, long long v)
{//在地址为i的结点表示的区间[tree[i].l, tree[i].r]中每个元素增加vtree[i].tag v;//增加标记tree[i].val (tree[i].r-tree[i].l1)*v;//区间[l, r]共有r-l1个元素每个元素增加v共增加(r-l1)*v。
}2 标记下传 如果需要访问线段树中当前结点的子结点则需要保证子结点的值val是正确的。 如果当前结点p的标记tag不为0则表示对当前结点p表示的区间存在一些修改操作而这些修改操作并没有作用到结点p的子孙结点。我们需要根据结点p的标记对结点p的子结点进行修改而后将结点p的标记归零这样就可以保证结点p的子结点的值就是该结点所表示区间的加和。
标记下传(pushDown)根据当前结点的标记tag更新该结点的子结点的标记tag与值val 具体步骤为
如果当前结点标记为0则返回。根据当前标记更新当前结点左右孩子的值并为左右孩子增加标记。当前结点标记清零。
void pushDown(int i)//地址为i的结点标记下传
{if(tree[i].tag 0)return;addTag(2*i, tree[i].tag);addTag(2*i1, tree[i].tag);tree[i].tag 0;
}2. 区间修改
区间修改操作为使a序列区间 [ l , r ] [l, r] [l,r]中的元素都增加数值v。 在线段树中访问到地址为i结点考虑区间修改操作如何影响当前结点表示的区间对应线段树中各结点的值。
如果当前结点表示的区间和区间 [ l , r ] [l, r] [l,r]不相交则直接返回。如果当前结点表示的区间完全被区间 [ l , r ] [l, r] [l,r]覆盖时只修改当前结点的标记和值不再修改其子孙。否则当前结点的左右孩子表示的区间都可能与区间 [ l , r ] [l, r] [l,r]有交集。在修改子孙结点前应该先进行标记下传pushDown操作更新孩子结点的标记和值。而后对当前结点的左右孩子进行对区间 [ l , r ] [l, r] [l,r]的区间修改操作。当前结点左右子树的值更新结束后再进行pushUp操作根据左右孩子的值更新当前结点的值。
该操作与区间查询的时间复杂度相同为 O ( log n ) O(\log n) O(logn)。
void update(int i, int l, int r, long long 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*i1, l, r, v);pushUp(i);//根据孩子的值更新结点i的值
}3. 区间查询
要查询a序列给定区间 [ l , r ] [l, r] [l,r]中元素的加和要做的是将 [ l , r ] [l, r] [l,r]区间划分为几个线段树中结点表示的区间将这些区间的值加和。 要在地址为i的结点表示的区间中返回 [ l , r ] [l, r] [l,r]中元素的加和
判断当前结点表示的区间和 [ l , r ] [l, r] [l,r]是否有交集。如果没有交集则返回。如果当前结点表示的区间完全被区间 [ l , r ] [l, r] [l,r]包含则返回当前结点的值。否则需要通过访问子结点来获取区间 [ l , r ] [l, r] [l,r]中元素的加和。 访问子结点前需要先进行标记下传pushDown操作。 而后分别在当前结点的两个子树中查询区间 [ l , r ] [l, r] [l,r]中元素的加和将二者的加和返回。 区间查询的时间复杂度为 O ( log n ) O(\log n) O(logn) (证明见洛谷 P3374 【模板】树状数组 1线段树解法)
//在地址为i的子树中查询区间[l, r]中所有元素的加和
long long query(int i, int l, int r)
{ if(tree[i].r l || tree[i].l r)return 0;if(l tree[i].l tree[i].r r)return tree[i].val; pushDown(i);//如果要访问结点i的孩子则标记下传return query(2*i, l, r)query(2*i1, l, r);
}注意本题数值范围达到 10 18 10^{18} 1018与数值相关的变量都要设为long long类型。
解法2树状数组
本解法不如使用线段树更加直观建议读者掌握上述线段树解法。树状数组解法仅作为参考。 原数组为数组a。对a数组的差分数组d建树状数组。 如果对原数组进行区间修改即对a序列区间 [ l , r ] [l, r] [l,r]中每个元素增加数值v在差分数组d数组上的操作为 d l d l v , d r 1 d r 1 − v d_l d_l v, d_{r1} d_{r1}-v dldlv,dr1dr1−v。 进行区间查询求a序列 [ l , r ] [l, r] [l,r]中所有元素的和可以借助a序列的前缀和求出。 记 a a a序列的前缀和为 s s s则a序列区间 [ l , r ] [l, r] [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_{x1}^ia_x six1∑iax a i ∑ x 1 i d x a_i \sum\limits_{x1}^id_x aix1∑idx 所以 s i ∑ x 1 i ∑ y 1 x d y s_i \sum\limits_{x1}^i\sum\limits_{y1}^xd_y six1∑iy1∑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_{x1}^i(\sum\limits_{y1}^id_y-\sum\limits_{yx1}^id_y)(\sum\limits_{y1}^id_y-\sum\limits_{y01}^id_y) x1∑i(y1∑idy−yx1∑idy)(y1∑idy−y01∑idy) ∑ x 0 i ( ∑ y 1 i d y − ∑ y x 1 i d y ) \sum\limits_{x0}^i(\sum\limits_{y1}^id_y-\sum\limits_{yx1}^id_y) x0∑i(y1∑idy−yx1∑idy) ∑ x 0 i ∑ y 1 i d y − ∑ x 0 i ∑ y x 1 i d y \sum\limits_{x0}^i\sum\limits_{y1}^id_y-\sum\limits_{x0}^i\sum\limits_{yx1}^id_y x0∑iy1∑idy−x0∑iyx1∑idy ( i 1 ) ∑ y 1 i d y − ∑ x 0 i ∑ y x 1 i d y (i1)\sum\limits_{y1}^id_y-\sum\limits_{x0}^i\sum\limits_{yx1}^id_y (i1)y1∑idy−x0∑iyx1∑idy ∑ x 0 i ∑ y x 1 i d y \sum\limits_{x0}^i\sum\limits_{yx1}^id_y x0∑iyx1∑idy ∑ y 1 i d y ∑ y 2 i d y . . . ∑ y i i d y \sum\limits_{y1}^id_y\sum\limits_{y2}^id_y...\sum\limits_{yi}^id_y y1∑idyy2∑idy...yi∑idy 1 d 1 2 d 2 . . . i d i ∑ y 1 i y ⋅ d y 1d_12d_2...id_i \sum\limits_{y1}^iy\cdot d_y 1d12d2...idiy1∑iy⋅dy
因此 s i ( i 1 ) ∑ y 1 i d y − ∑ y 1 i y ⋅ d y s_i (i1)\sum\limits_{y1}^id_y-\sum\limits_{y1}^iy\cdot d_y si(i1)y1∑idy−y1∑iy⋅dy
假想存在f序列 f i i ⋅ d i f_i i\cdot d_i fii⋅di 设两个树状数组 t 1 , t 2 t_1, t_2 t1,t2分别维护 d d d序列和 f f f序列的区间和。 进行单点修改时如果 d i d i v d_id_iv didiv那么 f i i ⋅ ( d i v ) f i i ⋅ v f_ii\cdot(d_iv)f_ii\cdot v fii⋅(div)fii⋅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(i1)s_d-s_f si(i1)sd−sf时间复杂度为 O ( log n ) O(\log n) O(logn)
【题解代码】
解法1线段树
#includebits/stdc.h
using namespace std;
#define N 100005
struct Node
{int l, r;long long val, tag;
} tree[4*N];
long long n, m, a[N];
void pushUp(int i)
{tree[i].val tree[2*i].valtree[2*i1].val;
}
void addTag(int i, long long v)//结点i增加标记v
{tree[i].tag v;tree[i].val (tree[i].r-tree[i].l1)*v;
}
void pushDown(int i)//标记下传
{if(tree[i].tag 0)return;addTag(2*i, tree[i].tag);addTag(2*i1, tree[i].tag);tree[i].tag 0;
}
void build(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 lr1;build(2*i, l, mid);build(2*i1, mid1, r);pushUp(i);
}
void update(int i, int l, int r, long long 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*i1, l, r, v);pushUp(i);
}
long long query(int i, int l, int r)//区间查询[l, r]中的值
{if(tree[i].r l || tree[i].l r)return 0;if(l tree[i].l tree[i].r r)return tree[i].val;pushDown(i);return query(2*i, l, r)query(2*i1, 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[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;
}解法2树状数组
#includebits/stdc.h
using namespace std;
#define N 100005
long long n, m, t1[N], t2[N];//t1[i]差分数组d的树状数组 t2[i]i*d[i]的树状数组
int lowbit(int x)
{return x -x;
}
void update(int i, long long v)//对c1、c2的单点修改
{for(int x i; x n; x lowbit(x))t1[x] v, t2[x] i*v;
}
void rangeUpdate(int l, int r, long long v)//对a的区间修改为对d的两个单点修改
{update(l, v);update(r1, -v);
}
long long sum(int n)//a的前n个元素的加和
{long long sd 0, sf 0;for(int x n; x 0; x - lowbit(x))sd t1[x], sf t2[x];return (n1)*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;
}
