题目
P3372 【模板】线段树 Ⅰ
P3373 【模板】线段树 Ⅱ
P3374 【模板】树状数组 Ⅰ
P3368 【模板】树状数组 Ⅱ
最近学习了一个十分基础之前觉得很高大上的数据结构——没错，就是线段树。首先，在这篇博客（登上了洛谷日报）浅谈线段树（Segment Tree） 以及 $Sparky$大佬 的帮助下，我终于摸到了线段树的门，，，在此总结一下线段树的学习。
线段树
基本概念
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为 $[a,\frac{a+b}{2}]$ ，右儿子表示的区间为 $ [\frac{a+b}{2} + 1, b] $。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。 使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为 $ O ( \log N）$ 。而未优化的空间复杂度为 $ 2N $，因此有时需要离散化让空间压缩。（来源百度）
当然，这都不重要，简言之，线段树是一种处理区间修改与查询的数据结构，他能解决形如
已知一个数列，你需要进行下面两种操作： 1.将某区间每一个数加上x 2.求出某区间每一个数的和
之类的问题
代码分析
开始胡乱分析，
在此以上述问题为例，分析一下线段树的基本代码组成
1.主函数
不多说直接上代码
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
scanf ("%d", &a[i]);
build (1, n, 1);//建树
for (int i = 1; i <= m; i++)
{
int t;
scanf ("%d", &t);
if (t == 1)
{
int x, y, v;
scanf ("%d %d %d", &x, &y, &v);
modify (1, n, 1, x, y, v);//修改
}
else
{
int x, y;
scanf ("%d %d", &x, &y);
printf("%lld\n", query (1, n, 1, x, y) );//查询
}
}
return 0;
}
2.建树
通过递归实现自下而上的建树，返回条件是只有一个点的时候，该点的 $tree[ ]$ 就是该点的价值
void build (int l, int r, int rt)
{
if (l == r)//返回条件：只有一个点时
{
tree[rt] = a[l];// a[] 就是读入的点的权值
return;
}
int m = (l+r) >> 1;
build (l, m, rt << 1);//左子树
build (m+1, r, rt << 1 | 1);//右子树
update (rt);//递归返回时处理，将叶结点上传
}
$ update $ 函数的编写如下 (据说 $inline$ 能加速，我也不知道是不是真的 )
inline void update (int rt)
{
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];//两个儿子的 tree 之和
}
另外，由于
l, m, rt << 1 //左子树
m+1, r, rt << 1 | 1 //右子树
之类的用法非常大量，在之后的程序以及下面的文章里，直接采用宏定义的手段简化代码
#define lson l, m, rt << 1 //左子树
#define rson m+1, r, rt << 1 | 1 //右子树
3.修改
将一个区间内所有的数增加一个值
修改一个大区间，如果修改的区间中包含了小区间，将小区间的 $tag[ ]$ 值增加 $v$ ，不然，将区间下放，直到访问到叶节点为止。（注意返回时还是要自下而上更新）
void modify (int l, int r, int rt, int b, int e, int v)
{
if (l == r)//访问到最下层时返回
{
tree[rt] += v;
return;
}
else
if (b <= l && r <= e)//当前区间 [l, r] 包含在目标修改区间 [b, e] 内
{
mark (l, r, rt, v);//修改区间 [l, r]
return;
}
demark (l, r, rt);//标记下放
int m = (l+r) >> 1;
if (b <= m)//目标区间包含在当前区间左子树内
modify (lson, b, e, v);//不要忘了之前的宏定义~~
if (e > m)//目标区间包含在当前区间右子树内
modify (rson, b, e, v);
update (rt);//递推返回时上传
return;
}
$ mark $ 与 $ demark $ 函数 如果为叶结点，直接赋值（不修改 $ tag [ ] $ ），不然直接修改 $ tag[ ] $ 以及 $ tree[ ] $，注意 $ tree[ ] $ （表示当前子树的值（某区间和）） 的修改要增加整个区间的值
//编号为 rt 的 [l, r] 的区间，整个增加 v
inline void mark (int l ,int r, int rt, long long v)
{
if (l == r)//只为叶结点
tree[rt] += v;
else
{
tag[rt] += v;
tree[rt] += (r - l + 1) * v; //注意增加整个区间的和
}
}
下放标记时，要注意将该节点的标记清零（若为乘法标记，要将值改为 $1$）
inline void demark (int l, int r, int rt)
{
int m = (l+r) >> 1;
mark (lson, tag[rt]);
mark (rson, tag[rt]);
tag[rt] = 0;//还原标记
}
4.询问
询问操作也通过递归实现，最后的返回也要将标记上传
long long query (int l, int r, int rt, int b, int e)//求和
{
//如果 所在区间[l, r] 被包含在 目标区间[b, e]内，直接返回
if (b <= l && r <= e)
return tree [rt];
demark (l, r, rt);//标记下放
int m = (l+r) >> 1;
long long ans = 0;
if (b <= m)
ans += query (lson, b, e);
if (e > m)
ans += query (rson, b, e);
update (rt);//返回时标记上传
return ans;
}
完整代码
//P3372 【模板】线段树 1
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 100000;
long long a[maxn + 9], tree[maxn*4 + 9], tag[maxn*4 + 9];
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
void build (int l, int r, int rt);
void modify (int l, int r, int rt, int b, int e, int v);
long long query (int l, int r, int rt, int b, int e);//求和
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
scanf ("%d", &a[i]);
build (1, n, 1);
for (int i = 1; i <= m; i++)
{
int t;
scanf ("%d", &t);
if (t == 1)
{
int x, y, v;
scanf ("%d %d %d", &x, &y, &v);
modify (1, n, 1, x, y, v);//modify -- 修改
}
else
{
int x, y;
scanf ("%d %d", &x, &y);
printf("%lld\n", query (1, n, 1, x, y) );
}
}
return 0;
}
inline void update (int rt)
{
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
void build (int l, int r, int rt)
{
if (l == r)
{
tree[rt] = a[l];
return;
}
int m = (l+r) >> 1;
build (lson);
build (rson);
update (rt);//递归返回时处理
}
inline void mark (int l ,int r, int rt, long long v)
{
if (l == r)
tree[rt] += v;
else
{
tag[rt] += v;
tree[rt] += (r - l + 1) * v;//注意增加整个区间的和
}
}
inline void demark (int l, int r, int rt)
{
int m = (l+r) >> 1;
mark (lson, tag[rt]);
mark (rson, tag[rt]);
tag[rt] = 0;
}
long long query (int l, int r, int rt, int b, int e)//求和
{
//如果 所在区间[l, r] 被包含在 目标区间[b, e]内，直接返回
if (b <= l && r <= e)
return tree [rt];
demark (l, r, rt);//标记下放
int m = (l+r) >> 1;
long long ans = 0;
if (b <= m)
ans += query (lson, b, e);
if (e > m)
ans += query (rson, b, e);
update (rt);//返回时标记上传
return ans;
}
//编号为 rt 的 [l, r] 的区间，整个增加 v
void modify (int l, int r, int rt, int b, int e, int v)
{
if (l == r)
{
tree[rt] += v;
return;
}
else
if (b <= l && r <= e)
{
mark (l, r, rt, v);
return;
}
demark (l, r, rt);//标记下放
int m = (l+r) >> 1;
if (b <= m)
modify (lson, b, e, v);
if (e > m)
modify (rson, b, e, v);
update (rt);
return;
}
其他题目
P3373 【模板】线段树 Ⅱ
已知一个数列，你需要进行下面三种操作： 1.将某区间每一个数乘上x 2.将某区间每一个数加上x 3.求出某区间每一个数的和
注意本题要用双标记，标记更新时有一个原则：
乘法标记更新，加法标记和乘法标记都要乘上更新值 加法标记更新，加法标记加上更新值
相当于线段树要打两遍
//P3373 【模板】线段树 2
#include <bits/stdc++.h>
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
using namespace std;
const int maxn = 100000;
long long a[maxn + 9], tree[maxn*4 + 9], tag_add[maxn*4 + 9], tag_mul[maxn*4 + 9];
//l r 正在一步步缩小的区间 ， b e 不变的需要查找的区间
void build (int l, int r, int rt);
void modify_mul (int l, int r, int rt, int b, int e, long long k);
void modify_add (int l, int r, int rt, int b, int e, long long k);
long long query (int l, int r, int rt, int b, int e);//查询区间 [b, e]
long long n, m, p;
int main()
{
cin >> n>> p;
for (int i = 1; i <= n; i++)
scanf ("%lld", &a[i]);
build (1, n, 1);
cin >> m;
for (int i = 1; i <= m; i++)
{
int t;
scanf ("%d", &t);
if (t == 1)
{
int x, y;
long long k;
scanf ("%d %d %lld", &x, &y, &k);
modify_mul (1, n, 1, x, y, k);
}
else if (t == 2)
{
int x, y;
long long k;
scanf ("%d %d %lld", &x, &y, &k);
modify_add (1, n, 1, x, y, k);
}
else if (t == 3)
{
int x, y;
scanf ("%d %d", &x, &y);
printf ("%lld\n", query(1, n, 1, x, y) % p );
}
}
}
void update (int rt)//上传操作
{
int ls = rt << 1;
int rs = rt << 1 | 1;
// int m = (l+r) >> 1;
//乘法优先
/* tree[rt] = tree[ls] * mul[ls] + add[ls] * (m - l + 1)
+ tree[rs] * mul[rs] + add[rs] * (r - m);*/
tree[rt] = (tree[ls] + tree[rs]) % p;
}
void build (int l, int r, int rt)
{
tag_mul[rt] = 1;//乘法标记要更新值 1
if (l == r)
{
tree[rt] = a[l];
return;
}
int m = (l+r) >> 1;
build (lson);
build (rson);
update (rt);
}
void mark_mul (int l, int r, int rt, long long v)
{
if (l == r)
tree[rt] = (tree[rt] * v) % p;
else
{
tag_mul[rt] = (tag_mul[rt] * v) % p;//两种标记以及本身的值都要乘
tag_add[rt] = (tag_add[rt] * v) % p;
tree[rt] = (tree[rt] * v) % p;
}
}
void mark_add (int l, int r, int rt, long long v)
{
if (l == r)
tree[rt] = (tree[rt] + v) % p;
else
{
tag_add[rt] = (tag_add[rt] + v) % p;//加法标记以及本身增加
tree[rt] = (tree[rt] + (r - l + 1) * v % p) % p;
}
}
void demark(int l, int r, int rt)//将标记下放
{
int m = (l+r) >> 1;
mark_mul (lson, tag_mul[rt]);
mark_mul (rson, tag_mul[rt]);
mark_add (lson, tag_add[rt]);
mark_add (rson, tag_add[rt]);
tag_mul[rt] = 1;//乘法标记要赋值1
tag_add[rt] = 0;
}
void modify_mul (int l, int r, int rt, int b, int e, long long v)
{
if (l == r)
{
tree[rt] = (tree[rt] * v) % p;
return;
}
else if (b <= l && r <= e)
{
mark_mul (l, r, rt, v);
return;
}
demark(l, r, rt);
int m = (l+r) >> 1;
if (b <= m)
modify_mul (lson, b, e, v);
if (e > m)
modify_mul (rson, b, e, v);
update (rt);
}
void modify_add (int l, int r, int rt, int b, int e, long long v)
{
if (l == r)
{
tree[rt] = (tree[rt] + v) % p;
return;
}
else if (b <= l && r <= e)
{
mark_add (l, r, rt, v);
return;
}
demark (l, r, rt);//再次下放
int m = (l+r) >> 1;
if (b <= m)
modify_add (lson, b, e, v);
if (e > m)
modify_add (rson, b, e, v);
update (rt);
}
long long query (int l, int r, int rt, int b, int e)//查询区间 b e
{
if (b <= l && r <= e)
return tree[rt];
// printf("-----%d %d %d %d\n", l, r, rt, tree[rt]);
demark(l, r, rt);
int m = (l+r) >> 1;
long long ans = 0;
if (b <= m)
ans = (ans + query (lson, b, e)) % p;
if (e > m)
ans = (ans + query (rson, b, e)) % p;
update (rt);
return ans;
}
P3374 【模板】树状数组 Ⅰ
如题，已知一个数列，你需要进行下面两种操作： 1.将某一个数加上x 2.求出某区间每一个数的和
本题完全可以用线段树的解法来写，注意赋值操作不用再考虑区间，直接修改最下的叶结点。
#include <iostream>
#include <cstdio>
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
using namespace std;
long long a[500000 + 9], tree[500000 * 4 + 9], tag[500000 * 4 + 9];
void build (int l, int r, int rt);
void modify_add (int l, int r, int rt, int p, int v);
long long query (int l, int r, int rt, int b, int e);
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
scanf ("%lld", &a[i]);
build (1, n, 1);
for (int i = 1; i <= m; i++)
{
int t, x, y;
scanf ("%d %d %d", &t, &x, &y);
if (t == 1)
modify_add (1, n, 1, x, y);
if (t == 2)
printf ("%lld\n", query(1, n, 1, x, y) );
}
}
void mark (int l, int r, int rt, long long v)
{
if (l == r)
{
tree[rt] += v;
}
else
{
tag[rt] += v;
tree[rt] += (r - l + 1) * v;
}
}
void demark (int l, int r, int rt)
{
int m = (l+r) >> 1;
mark (lson, tag[rt]);
mark (rson, tag[rt]);
tag[rt] = 0;
}
void update (int rt)
{
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
void build (int l, int r, int rt)
{
if (l == r)
{
tree[rt] = a[l];
return;
}
int m = (l+r) >> 1;
build (lson);
build (rson);
update (rt);
}
void modify_add (int l, int r, int rt, int p, int v)
{
if (l == r)//改为单点修改 ~~
{
tree[rt] += v;
return;
}
int m = (l+r) >> 1;
if (p <= m)
modify_add (lson, p, v);
if (p > m)
modify_add (rson, p, v);
update (rt);
}
long long query (int l, int r, int rt, int b, int e)
{
if (b <= l && r <= e)
return tree[rt];
demark (l, r, rt);//下放
int m = (l+r) >> 1;
long long ans = 0;
if (b <= m)
ans += query (lson, b, e);
if (e > m)
ans += query (rson, b, e);
update (rt);
return ans;
}
P3368 【模板】树状数组 Ⅱ
如题，已知一个数列，你需要进行下面两种操作： 1.将某区间每一个数数加上x 2.求出某一个数的和
和线段树相比，也只是修改一下查询函数
#include <iostream>
#include <cstdio>
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
using namespace std;
long long a[500000 + 9], tree[500000 * 4 + 9], tag[500000 * 4 + 9];
void build (int l, int r, int rt);
void modify_add (int l, int r, int rt, int b, int e, int v);
long long query (int l, int r, int rt, int x);
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
scanf ("%lld", &a[i]);
build (1, n, 1);
for (int i = 1; i <= m; i++)
{
int t, x, y, k;
scanf ("%d", &t);
if (t == 1)
{
scanf ("%d %d %d", &x, &y, &k);
modify_add (1, n, 1, x, y, k);
}
if (t == 2)
{
scanf ("%d", &x);
printf ("%lld\n", query(1, n, 1, x) );
}
}
}
void mark (int l, int r, int rt, long long v)
{
if (l == r)
{
tree[rt] += v;
}
else
{
tag[rt] += v;
tree[rt] += (r - l + 1) * v;
}
}
void demark (int l, int r, int rt)
{
int m = (l+r) >> 1;
mark (lson, tag[rt]);
mark (rson, tag[rt]);
tag[rt] = 0;
}
void update (int rt)
{
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
void build (int l, int r, int rt)
{
if (l == r)
{
tree[rt] = a[l];
return;
}
int m = (l+r) >> 1;
build (lson);
build (rson);
update (rt);
}
void modify_add (int l, int r, int rt, int b, int e, int v)
{
if (l == r)
{
tree[rt] += v;
return;
}
if (b <= l && r <= e)
{
mark (l, r, rt, v);
return ;
}
int m = (l+r) >> 1;
if (b <= m)
modify_add (lson, b, e, v);
if (e > m)
modify_add (rson, b, e, v);
update (rt);
}
long long query (int l, int r, int rt, int x)
{
if (l == r)
return tree[rt];
demark (l, r, rt);//下放
int m = (l+r) >> 1;
long long ans = 0;
if (x <= m)
ans += query (lson, x);
if (x > m)
ans += query (rson, x);
update (rt);
return ans;
}
完结撒花~ ~ ~
