知识点

---

---

模板题

1 . 基础版：洛谷 P3372 【模板】线段树 1 

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 k。
2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 n, m，分别表示该数列数字的个数和操作的总个数。

第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。

接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下：

1. 1 x y k：将区间 [x, y] 内每个数加上 k。
2. 2 x y：输出区间 [x, y] 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例

输入 #1

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

输出 #1

11
8
20

说明/提示

对于 30% 的数据：n⩽8" role="presentation" style="position: relative;">n⩽8$n⩽8$，m⩽10" role="presentation" style="position: relative;">m⩽10$m⩽10$。
对于 70% 的数据：n⩽103" role="presentation" style="position: relative;">n⩽103$n⩽{10}^3$，m⩽104" role="presentation" style="position: relative;">m⩽104$m⩽{10}^4$。
对于 100% 的数据：1⩽n,m⩽105" role="presentation" style="position: relative;">1⩽n,m⩽105$1⩽n,m⩽{10}^5$。

保证任意时刻数列中任意元素的和在[−263,263)" role="presentation" style="position: relative;">[−263,263)$[-2^{63},2^{63})$内。

【样例解释】

---

直接暴力解决可以得到70分，后面的数据特别大，一个数一个数得增加会导致TLE：

#include 
#include 
#include 
#include 
using namespace std;
int n,m;
const int maxn=1e7+5;
int a[maxn];
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
 
inline int write(int x)
{
	if(x>9) write(x/10);
	return putchar(x%10+'0');
}
 
int main()
{
	n=read(); m=read();
	for(register int i=1;i<=n;++i)
	{
		a[i]=read();
	}
 
	for(register int i=1;i<=m;++i)
	{
		int num=read();
		if(num == 1)
		{
			int x=read(),y=read(),k=read();
			for(register int j=x;j<=y;++j)
			{
				a[j]+=k;
			}
		}
 
		else if(num == 2)
		{
			int x=read(),y=read(),sum=0;
			for(register int j=x;j<=y;++j)
			{
				sum+=a[j];
			}
			write(sum);
			putchar('\n');
		}
	}
	return 0;
}

通过剩下的数据需要采用线段树这个数据结构 ：
 

#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
int n,m;
const int maxn=1e6+5;
int a[maxn];
struct node
{
	ll int left,right,sum,lazy;
}tree[maxn<<2];
 
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
 
inline void build(int num,int l,int r)
{
	tree[num].left=l; tree[num].right=r; //记录正在搜索的区间的左右节点
	if(l == r) 
    //l==r时说明它就是最下层叶子节点，即只代表一个数，那么我们就将a数组的第l或r个元素映射上去。
	{
		tree[num].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build((num<<1),l,mid); //建立左子树
	build((num<<1|1),mid+1,r); //建立右子树
	tree[num].sum=tree[num<<1].sum+tree[num<<1|1].sum; 
        //sum表示这段区间的区间和，所以这个节点的sum值等于它的儿子节点的值之和。
}
 
inline void put(int num)
{
     //下传左儿子。
	tree[num<<1].lazy+=tree[num].lazy;
	tree[num<<1].sum+=(tree[num<<1].right-tree[num<<1].left+1)*tree[num].lazy;
       //下传右儿子。
	tree[num<<1|1].lazy+=tree[num].lazy;
	tree[num<<1|1].sum+=(tree[num<<1|1].right-tree[num<<1|1].left+1)*tree[num].lazy;
	tree[num].lazy=0; //将该点的标记清零
}
 
inline void update(int num,int l,int r,int k)
{
	if((tree[num].rightr)) return;
         //如果需要访问的区间和现在所遍历到的这个区间完全不重合，那么返回，相当于剪枝。
	if((tree[num].right<=r)&&(tree[num].left>=l)) 
	{
		tree[num].lazy+=k;
		tree[num].sum+=(tree[num].right-tree[num].left+1)*k;
		return;
	}
    //如果需要访问的区间和当前遍历到的区间重合，那么就直接把lazy和sum更新后返回，无需再向下查找
	if(tree[num].lazy>0)
	{
		put(num); //之前遍历过，标记下传。
	} 
	update((num<<1),l,r,k);
	update((num<<1|1),l,r,k); //递归更新左右儿子
	tree[num].sum=tree[num<<1].sum+tree[num<<1|1].sum; 
                //递归回来后将左右子节点的sum加起来赋给父节点的sum。
}
 
inline ll int query(int num,int l,int r) //查找执行操作的结果，判断条件与合并的条件相同
{
	if((tree[num].rightr)) return 0;
	if((tree[num].right<=r)&&(tree[num].left>=l)) return tree[num].sum;
	if(tree[num].lazy>0)
	{
		put(num);
	}
	return query((num<<1),l,r)+query((num<<1|1),l,r);
}
 
int main()
{
	n=read(); m=read();
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
	}
	build(1,1,n);
	for(int i=1;i<=m;++i)
	{
		int num=read();
		if(num == 1)
		{
			int x=read(),y=read(),k=read();
			update(1,x,y,k);
		}
		else if(num == 2)
		{
			int x=read(),y=read();
			ll int sum;
			sum=query(1,x,y);
			printf("%lld\n",sum);
		}
	}
	return 0;
}

---

2 . 提高版：洛谷 P3373 【模板】线段树 2

题目描述

如题，已知一个数列，你需要进行下面三种操作：

• 将某区间每一个数乘上 x

• 将某区间每一个数加上 x

• 求出某区间每一个数的和

输入格式

第一行包含三个整数 n,m,p，分别表示该数列数字的个数、操作的总个数和模数。

第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。

接下来 m 行每行包含若干个整数，表示一个操作，具体如下：

操作 1： 格式：1 x y k  含义：将区间 [x,y] 内每个数乘上 k

操作 2： 格式：2 x y k  含义：将区间 [x,y] 内每个数加上 k

操作 3： 格式：3 x y  含义：输出区间 [x,y] 内每个数的和对 p 取模所得的结果

输出格式

输出包含若干行整数，即为所有操作 3 的结果。

输入输出样例

输入 #1

5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4

输出 #1

17
2

说明/提示

【数据范围】

对于 30% 的数据：n⩽8" role="presentation" style="position: relative;">n⩽8$n⩽8$，m⩽10" role="presentation" style="position: relative;">m⩽10$m⩽10$
对于 70% 的数据：n⩽103" role="presentation" style="position: relative;">n⩽103$n⩽{10}^3$，m⩽104" role="presentation" style="position: relative;">m⩽104$m⩽{10}^4$
对于 100% 的数据：n⩽105" role="presentation" style="position: relative;">n⩽105$n⩽{10}^5$，m⩽105" role="presentation" style="position: relative;">m⩽105$m⩽{10}^5$

除样例外，p = 571373

（数据已经过加强^_^）

样例说明：

故输出应为 17、2（ 40mod38=2" role="presentation" style="position: relative;">40mod38=2$40mod38=2$ ）

---