该笔记还处于基础部分，待日后继续深入整理……

该笔记目前直接复制的之前的笔记，还未调整格式。页面格式、内容、链接等可能存在混乱错误……

简介

是一种用来维护 区间信息 的数据结构。

可以实现的操作：

单点、区间修改
区间查询（区间求和、最大值、最小值）
等等

描述

线段树会将一个非点区间（即长度大于$1$）利用递归的思想，二分为两个子区间来进行操作。
这样就会将一个线段划分转化成一个树形结构。

线段树描述
其中：紫色的a[]是原数组，红色的d[]是线段树：存储的区间的和，黄色范围代表管辖区间。

每个节点会存储并维护其所管辖的区间的当前信息。（如上图存的就是区间的和）
可根据题目要求，确定自己所需存储维护的信息。

实现方法

提前的宏定义

#define NOW_Node node[index]		//代表当前节点
#define NOW_LSon node[index].sonL	//代表当前节点左儿子下标
#define NOW_RSon node[index].sonR	//代表当前节点右儿子下标

0x00 建树

基本认识

根据上图可发现几个要点：

每一个节点i的左儿子下标是2i，右儿子下标是2i+1。
记：i管辖的区间为$[s,t]$。
令：$mid=\frac{s+t}{2}$。
则左儿子2i管辖区间为$[s,mid]$，右儿子2i+1管辖区间为$[mid+1,t]$。

实现方法

之前已经介绍了递归的思想，那么只需要确定递归边界。
由上图很容易看出，递归边界就是当长度为$1$的点。

记：当前点为node[index]，代表区间为$[l,r]$。原数组为arr[]
当$l=r$的时候，说明到达递归边界，这个时候的值直接为对应区间的值。
也就是node[index] = arr[r]

因为二分的操作使得递归的深度不会大于$log(n)$，故完全可以采用递归的方式简化代码，不用担心递归的栈溢出等缺点。

储存方法

方法1、

struct typeNode
{
	int val, L, R, mid, len;	//val代表储存的值，L、R分别代表区间左、右端点，mid代表区间中点，len代表区间长度
}node[4*N];

直接用左儿子下标为2i，右儿子下标为2i+1转递。
函数为build(int index, int l, int r)，建左儿子用则为build(2*i, l, r)。

空间范围：反正直接把长度设置为$4n$。
因为该线段树深度为$\lceil log(n) \rceil$，又因为为完全二叉树，总节点个数为$2^{\lceil log(n) \rceil +1}-1$。但建树的时候最后一层不一定从左往右建，也可能很右边会有一个，所以要预留出所有的最后一层的节点位置，即开$4N$。
具体分析见关于线段树的数组到底是开2N还是4N。

方法2、

struct typeNode
{
	int val, L, R, mid, len, sonL, sonR;	//多了个sonL和sonR，代表左儿子的index和右儿子的index
}node[2*N];

build()的时候需要多一个计数器变量cnt，记录总过有多少节点。
函数为build(int &index, int l, int r)。其中传引用会在伪代码中解释。
这里多存了个左儿子和右儿子的下标，使得可以保证从按顺序建，不会出现空间浪费，于是可以开$2N$。
相较于方法2空间消耗会少一点。

以下采用“方法2”的方式来储存。

伪代码

struct typeSegment{
	int cnt = 0;	//记录node节点的数量，便可实现按顺序建树

	struct typeNode{
		int val, L, R, len, mid, sonL = 0, sonR = 0;
	} node[N * 2];

	void build(int &index, int L, int R) //对区间[L,R]建立节点，下标为index
	{
		index = ++cnt;
		/*引用index的原因：
		这里因为引用index，在递归时会直接把seg[index].son_赋值为某儿子的index。
		*/
		NOW_Node.L = L, NOW_Node.R = R, NOW_Node.mid = (L + R) >> 1, NOW_Node.len = R - L + 1;//节点基本信息

		if (L == R)
			NOW_Node.val = arr[R]; //为递归边界，直接为对应区间的值
		else
		{
			build(NOW_LSon, L, NOW_Node.mid);
			//划分建立左区间，注意这里传的index是sed[index].lson
			build(NOW_RSon, NOW_Node.mid + 1, R);
			//划分建立右区间
			NOW_Node.val = node[NOW_LSon].val + node[NOW_RSon].val;
			//计算该区间信息
		}
	}
}Segment;	//直接用个总结构体，便于模板化。//其实就是个个人癖好orz……

0x01 区间查询

对区间进行值的条件查询，如对区间$[L,R]$求总和，求区间最值等操作。

实现方法

将要查询的区间，拆成几个在其范围里的节点的区间进行求解计算。（类似于分块思想）

如果当前区间完全在查询区间的范围里，则直接返回这个区间的值。
如果不是，则分别查询左右区间计算最终值。
- 如果查询区间的左端点小于等于当前区间中点，则查询范围会存在于左儿子区间里，要查询左儿子。
- 如果查询区间的右端点大于当前区间中点，则查询范围会存在于右儿子区间里，要查询右儿子。
  
  注意：这里为大于！因为中点是算在左区间里的！……

【直接给代码吧ヾ(•ω•`)o……

伪代码

int query(int index, const int &q_L, const int &q_R)
{
	if (q_L <= NOW_Node.L && q_R<= NOW_Node.R) return NOW_Node.val;
	//当前区间直接在查询区间里，直接返回值
	//【我查了，一句返回了，有什么好说的……
	
	//↓ 不完全包含于查询区间里，就要查询两子区间的值计算
	int tmpAns = 0;
	if (q_L <= NOW_Node.mid) tmpAns += query(NOW_LSon, q_L, q_R);
	//如果要查询区间左端点，比当前区间的中点还大，证明左儿子区间完全不在
	if (q_R > NOW_Node.mid) tmpAns += query(NOW_RSon, q_L, q_R);	//为>，不是>=
	return tmpAns;
}

0x02 区间修改

对区间进行值的修改，如区间$[L,R]$加上或乘上一个数。

(最初)实现方法

跟查询的方法一样，找到对应区间后直接修改值。

但注意，如果不是长度为1的区间，值的修改要乘上对应修改区间的长度。

比如对$[1,2]$这个区间加上$2$。

$[1,1]$和$[2,2]$这两个子区间会加$2$。
但$[1,2]$则个大的区间应该加的就是$4$。

同理，$[1,4]$这个大区间就该加$8$了。

缺点分析

【诶我说停停，先别着急写啊，不要啪的一下就写起来了很快啊……

如果碰上这样的情况：

对区间$[1,10000]$加上$10000$次$233$。

查询区间$[23333,23333]$的值。

怎么样，有没有觉得自己被耍了！

所以如果当老实人，他让我们修改区间，我们就老老实实修改区间，可是要吃大亏的。【指TLE……

改进方法

所以他耍我们，我们也耍一下他xd。

不是让我们对区间修改吗，我们就先偷下懒：不老老实实地全部修改完，只做个记号在那。
等到他让我们真正查询这个区间的时候，我们也才真正的去修改，并返回查询值。【并且注意lazy清零！……

这便是lazy懒标记的由来。

但我们该怎么偷懒呢？

如果当前区间完全在修改区间的范围里，我们便可以按分析的那样，先把修改的值加到lazy里。等之后有需要再去真正地修改，即“下放lazy”。
如果不是，这里就需要注意，我们再直接加到lazy标记的话，有些明明不该修改的区间就会被修改。所以这里的懒就偷不得，就要真正的修改当前节点的值，并尝试修改子节点。（但如果儿子可以偷懒，就让儿子去偷懒）
- 如果修改区间的左端点大于当前区间中点，则不会修改左儿子区间。
- 如果修改区间的右端点小于等于当前区间中点，则不会修改右儿子区间。

伪代码

区间修改：

struct typeNode{
	int ..., lazy;	//这里多定义个lazy，用来存偷懒没修改的值
}

void modify(int index, const int &m_L, const int &m_R, const int &m_val)
{
	if (m_L <= NOW_Node.L && NOW_Node.R <= m_R)
		NOW_Node.lazy += m_val;	//当前区间完全在范围里，直接偷懒
	else
	{
		NOW_Node.val += (min(m_R, NOW_Node.R) - max(m_L, NOW_Node.L) + 1) * m_val;	
		/*
		这里是修改所包含区间的值
		如要修改[4,9]，当前节点区间是(1,6)	//这里为了区分用的小括号，实际上包含端点
		则只会修改[4,6)，也就是val += (6 - 4 + 1) * 2
		*/
		if (m_L <= NOW_Node.mid) modify(NOW_LSon, m_L, m_R, m_val);
		if (m_R > NOW_Node.mid) modify(NOW_RSon, m_L, m_R, m_val);
	}
}

有lazy的区间查询：

struct typeNode{

	...

	void pushdown(typeSegment *Segment)	//下放也不用太彻底，能摸一层是一层xd……
	{
		val += len * lazy;	
		if (sonL) Segment.modify(sonL, L, mid, lazy);
		//存在子节点才下放【不然我这种结构就会无限下放_(:з」∠)_……
		if (sonR) Segment.modify(sonR, mid + 1, R, lazy);
		lazy = 0;	//！lazy注意清零！
	}
}

int query(int index, const int &q_L, const int &q_R)
{
	if (NOW_Node.lazy) NOW_Node.pushdown(*this);	//注意查询的时候，只要有懒标记就必下放【别人都来查岗了你还摸鱼.jpg……

	if (q_L <= NOW_Node.L && NOW_Node.R <= q_R)		//以下跟普通的查询操作一样
		return NOW_Node.val;
	int tmpAns = 0;
	if (q_L <= NOW_Node.mid) tmpAns += query(NOW_LSon, q_L, q_R);
	if (q_R > NOW_Node.mid) tmpAns += query(NOW_RSon, q_L, q_R);
	return tmpAns;
}

Tip: 我这里的偷懒是直接连本身都先不修改，而在下放的时候才修改；其他人有些可能会先修改自身。算是个小优化，注意区分一下……

最终代码

洛谷P3372 【模板】线段树 1

#include <bits/stdc++.h>

#define N 100000

#define NOW_Node node[index]	  //代表当前节点
#define NOW_LSon node[index].sonL //代表当前节点左儿子下标
#define NOW_RSon node[index].sonR //代表当前节点右儿子下标
using namespace std;
long long arr[N + 5];
struct typeSegment
{
	int cnt = 0; //记录node节点的数量，便可实现按顺序建树

	struct typeNode
	{
		long long val;
		int L, R, len, mid, sonL = 0, sonR = 0, lazy = 0;

		void pushdown(typeSegment &Segment) //下放也不用太彻底，左右儿子仍加到lazy里。【能摸一层是一层xd……
		{
			val += len * lazy;
			if (sonL)
				Segment.modify(sonL, L, mid, lazy); //存在子节点才下放【不然我这种结构就会无限下放
			if (sonR)
				Segment.modify(sonR, mid + 1, R, lazy);
			lazy = 0; //lazy注意清零。
		}
	} node[N * 2];

	void build(int &index, int L, int R) //对区间[l,r]建立节点，下标为index
	{
		index = ++cnt;
		//引用原因：
		//这里因为引用index的原因，在递归时会直接把seg[index].lson赋值为左儿子的index。
		NOW_Node.L = L, NOW_Node.R = R,
		NOW_Node.mid = (L + R) >> 1, NOW_Node.len = R - L + 1;
		//节点基本信息
		if (L == R)
			NOW_Node.val = arr[R]; //为递归边界，直接为对应区间的值
		else
		{
			build(NOW_LSon, L, NOW_Node.mid);
			//划分建立左区间，注意这里传的index是sed[index].lson
			build(NOW_RSon, NOW_Node.mid + 1, R);
			//划分建立右区间
			NOW_Node.val = node[NOW_LSon].val + node[NOW_RSon].val;
			//计算该区间信息
		}
	}

	void modify(int index, const int &m_L, const int &m_R, const int &m_val)
	{
		if (m_L <= NOW_Node.L && NOW_Node.R <= m_R)
			NOW_Node.lazy += m_val; //当前区间完全在范围里，直接偷懒。
		else
		{
			NOW_Node.val += (min(m_R, NOW_Node.R) - max(m_L, NOW_Node.L) + 1) * m_val;
			/*
			这里是修改所包含区间的值
			如要修改[4,9]，当前节点区间是(1,6)	//这里为了区分用的小括号，实际上包含端点
			则只会修改[4,6)，也就是val += (6 - 4 + 1) * 2
			*/
			if (m_L <= NOW_Node.mid)
				modify(NOW_LSon, m_L, m_R, m_val);
			if (m_R > NOW_Node.mid)
				modify(NOW_RSon, m_L, m_R, m_val);
		}
	}

	long long query(int index, const int &q_L, const int &q_R)
	{
		if (NOW_Node.lazy) //注意查询的时候，只要有懒标记就必下放【别人都来查岗了你还摸鱼.jpg……
			NOW_Node.pushdown(*this);
		if (q_L <= NOW_Node.L && NOW_Node.R <= q_R)
			return NOW_Node.val;
		//当前区间直接在查询区间里，直接返回值//【我查了，一句返回了，有什么好说的……

		//↓ 不完全包含于查询区间里，就要查询两子区间的值计算
		long long tmpAns = 0;
		if (q_L <= NOW_Node.mid)
			tmpAns += query(NOW_LSon, q_L, q_R);
		//如果要查询区间左端点，比当前区间的中点还大，证明左儿子区间完全不在
		if (q_R > NOW_Node.mid)
			tmpAns += query(NOW_RSon, q_L, q_R);
		return tmpAns;
	}
} Segment; //直接用个大的结构体，便于模板化。
int main()
{
	int n, m, tmp, w, l, r, i;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		scanf("%lld", &arr[i]);
	Segment.build(tmp, 1, n);
	//Segment.test(1);
	while (m--)
	{
		scanf("%d", &w);
		if (w == 1)
		{
			scanf("%d%d%d", &l, &r, &i);
			Segment.modify(1, l, r, i);
		}
		else
		{
			scanf("%d%d", &l, &r);
			printf("%lld\n", Segment.query(1, l, r));
		}
	}
}