题目链接：P3372 【模板】线段树 1 – 洛谷
一.定义：
1.线段树是一棵由线段组成的树（分治与二叉树的结合体）
2.线段树是一种二叉搜索树。什么叫做二叉搜索树？首先满足二叉树，每个结点度<=2，即每个结点最多有两颗子树。何为搜索，我们要知道，线段树的每个结点都存储了一个区间，也可以理解成一个线段，而搜索，就是在这些线段上进行搜索操作得到你想要的答案。
二.特征：
1.用分治法自顶向下建立，每次分治，左右子树各一半。
2.每个节点都表示一个“线段”区间，非叶子节点包含多个元素，叶子节点只包含一个元素。
3.除了最后一层，其他层都是满的。—–>近似完全二叉树，可以用数组存树。用一个数组tree[]存储节点。若一个节点的存储下标为k ，则其左子节点的下标为2k ，其右子节点的下标为2k +1。 4.l=r，说明这是一个叶子节点。
5.l<r，说明他有两个子节点，左儿子[l,m],右儿子[m+1,r]，其中m=(l+r)/2;
三.作用：
线段树看起来挺麻烦的，他为什么这么高效？ 每个结点的值，代表了以它为根的子树上所有节点的值，那么，查询这个子树所代表的区间的值时，就不必遍历整棵树，而是直接读取这棵子树的根值就行了。并且树形结构的操作时间复杂度是O(logn)。 线段树最适合解决的问题的特征是：大区间的解可以从小区间的解合并而来。 线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。 线段树可以在 O(log N) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
四.建树：
首先，我们得先明白几件事情。 每个结点存什么，如何存树，如何建树？
（1）一个结点对应一段区间[l,r]，区间内有我们需要的值（区间和，最值等等），所以一个结点内要保存该结点对应区间的左右边界，需要的值。
（2）线段树近似完全二叉树，可以用数组存树。用一个数组tree[]存储节点。若一个节点的存储下标为o ，则其左子节点的下标为2o ，其右子节点的下标为2o +1。
（3）建树：以n个元素的区间(a[n])为基础建树。以维护区间和为例： tree[]数组大小：4*n（可能存在空间浪费) 基于递归建树。初始节点为1，因为你要从1号节点开始建树。左子树节点是o*2，右子树节点是o*2+1。线段树在构造子树时，一个结点的两个子节点是平分这个子树的（特征中说过）在遍历时，左子树范围是[l,m],右子树是 [m+1,r],其中：m=(l+r)/2。 线段树建树的时间复杂度为O(n)
五.区间修改：
区间修改操作：单点修改+区间修改
在一开始建树的时候该点是在树中的，树中一个点改变可能会引起这棵树的改变。还是以区间求和为例，当你改变了一个点，这个点的所有父节点都得改变。（如图）
先递归找到要修改的叶子节点，直接修改叶子节点上元素的值，然后从底往上更新线段树即可
但是这样操作时间复杂度最坏是O(n)，所以我们还需进行优化
六.区间查询：
区间查询：直接递归查询即可。但是在查询过程中要注意懒标记。 完全覆盖和部分覆盖两种情况
无懒标记的线段树代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\\n"
int n, m;
const int N = 1e5 + 10;
int a[N];
//线段树的结点结构
struct Node
{
int l, r;
int sum;
} tree[N << 2];
void Build(int i, int le, int ri) // 构建第i号节点，对应的区间[le,ri],时间复杂度O(n);
{//建立线段树
tree[i].l = le;
tree[i].r = ri;
if(le==ri)
{//区间中只有一个数据 叶子节点
tree[i].sum = a[le];
return;
}
//区间中有多个数据 非叶子节点
int mid = (le + ri) / 2;
Build(2 * i, le, mid);
Build(2 * i + 1, mid + 1, ri);
tree[i].sum = tree[2 * i].sum + tree[2 * i + 1].sum;
}
void Update(int i,int le,int ri,int k)
{//区间修改->最坏的情况下退化成O(n)–>保持logn:懒标记
if(tree[i].l==tree[i].r)
{//叶子节点的修改
tree[i].sum += k;
return;
}
int mid = (tree[i].l + tree[i].r) / 2;
if(le<=mid)//如果左孩子对应的区间有修改的部分，先修改左孩子
{
Update(2 * i, le, ri, k);
}
if(mid+1<=ri)//如果右孩子对应的区间有修改的部分，先修改右孩子
{
Update(2 * i + 1, le, ri, k);
}
tree[i].sum = tree[2 * i].sum + tree[2 * i + 1].sum;
}
int query(int i,int le,int ri)
{//查询[le,ri]
int ans = 0;
if(tree[i].l>=le&&tree[i].r<=ri){
//第i个节点对应的区间被查询的区间完全覆盖，第i个节点对应的区间和要被算到答案里面
return tree[i].sum;
}
else
{//第i个节点对应的区间没有被查询的区间完全覆盖
int mid = (tree[i].l + tree[i].r) / 2;
if(le<=mid)
{
ans += query(2 * i, le, ri);
}
if(ri>=mid+1)
{
ans += query(2 * i + 1, le, ri);
}
return ans;
}
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n;i++)
{
cin >> a[i];
}
Build(1, 1, n); // 从根节点开始建树 根节点1号节点[1,n];
int q, x, y, k;
while(m–){
cin >> q;
if(q==1)
{
cin >> x >> y >> k;
Update(1, x, y, k);
}
else
{
cin >> x >> y;
int ans = query(1, x, y);
cout << ans << endl;
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T–)
{
solve();
}
return 0;
}
七.懒标记：
为了降低时间复杂度，我们引进一个新玩意：lazy-tag懒标记。tag[i]记录了区间i的修改，这样就不用一个一个的再去修改去区间的内的每个元素了。也可以直接在结构体中加tag属性。 那啥时候修改？一会再修改。 既然不一个个的改，那我们就改整体！ 当我们进行修改时，先只对这个线段区间上进行整体上的修改，其内部每个元素的值先不修改。只有当查找到的区间[l,r]不包含在给定的区间[L,R]时（即l<L||r>R时），才把变化值传给下一层的子区间，即修改内部元素。（完全覆盖，部分覆盖）
八.down函数
down这个函数，也就是当需要查询某个结点的子树时，需要用到这个函数，函数功能就是更新子树的lazy值，可以理解为平时先把事情放着，等到哪天要检查的时候，就临时再去做，而且做也不是一次性做完，检查哪一部分它就只做这一部分。是不是感受到了什么是Lazy_tag，实至名归
带有懒标记的线段树：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\\n"
int n, m;
const int N = 1e5 + 10;
int a[N];
//线段树的结点结构
struct Node
{
int l, r;
int sum;
int lazy_tag; //lazy_tag==0说明该节点对应的区间没有被修改过，!=0被修改过
} tree[N << 2];
void pushup(int i)
{//合并左右子节点的信息到父节点
tree[i].sum = tree[2 * i].sum + tree[2 * i + 1].sum;
}
void Build(int i, int le, int ri) // 构建第i号节点，对应的区间[le,ri],时间复杂度O(n);
{//建立线段树
tree[i].l = le;
tree[i].r = ri;
if(le==ri)
{//区间中只有一个数据 叶子节点
tree[i].sum = a[le];
return;
}
//区间中有多个数据 非叶子节点
int mid = (le + ri) / 2;
Build(2 * i, le, mid);
Build(2 * i + 1, mid + 1, ri);
pushup(i);
}
void apply(int i,int k)
{//将懒标记应用到当前节点
tree[i].lazy_tag += k; // 有可能连续多次修改
tree[i].sum += (tree[i].r – tree[i].l + 1) * k;
}
void pushdown(int i)
{
if (tree[i].lazy_tag != 0)
{
apply(2 * i, tree[i].lazy_tag);
apply(2 * i + 1, tree[i].lazy_tag);
tree[i].lazy_tag = 0;
}
}
void Update(int i, int le, int ri, int k)
{
// 引入懒标记->保持在O(logn);
if(tree[i].l>=le&&tree[i].r<=ri)
{//第i个节点对应的区间被要修改的区间完全覆盖
apply(i, k);
return;
}
else
{
pushdown(i);//下传懒标记，把第i个节点的两个孩子对应的区间把之前欠的先修改了
int mid = (tree[i].l + tree[i].r) / 2;
if(le<=mid)
{
Update(2 * i, le, ri, k);
}
if(ri>=mid+1)
{
Update(2 * i + 1, le, ri, k);
}
pushup(i);
}
}
int query(int i, int le, int ri)
{ // 查询[le,ri]
int ans = 0;
if (tree[i].l >= le && tree[i].r <= ri)
{
// 第i个节点对应的区间被查询的区间完全覆盖，第i个节点对应的区间和要被算到答案里面
return tree[i].sum;
}
else
{ // 第i个节点对应的区间没有被查询的区间完全覆盖
pushdown(i); // 下传懒标记，把第i个节点的两个孩子对应的区间把之前欠的先修改了
int mid = (tree[i].l + tree[i].r) / 2;
if (le <= mid)
{
ans += query(2 * i, le, ri);
}
if (ri >= mid + 1)
{
ans += query(2 * i + 1, le, ri);
}
return ans;
}
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n;i++)
{
cin >> a[i];
}
Build(1, 1, n); // 从根节点开始建树 根节点1号节点[1,n];
int q, x, y, k;
while(m–){
cin >> q;
if(q==1)
{
cin >> x >> y >> k;
Update(1, x, y, k);
}
else
{
cin >> x >> y;
int ans = query(1, x, y);
cout << ans << endl;
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T–)
{
solve();
}
return 0;
}
