线段树知识总结

线段树这个东西，这次是第二次学习，怎么说呢，感觉理解还是不是特别的透彻，因此，在后面彻底完学习之后这个东西再改成公开

线段树概念引入

线段树是一种数据结构，其并不算是一种算法，而是一种减小时间复杂度的工具，我们可以将正常的区间修改和查询的O(N)的时间复杂度，缩短到O(logN)的级别，因此，线段树是一个在处理区间问题上是一个很好的工具

通常用于解决区间查询和更新的问题。它可以高效地处理动态数组或者静态数组的区间操作问题，例如区间最小值、最大值、区间和等。

线段树能够解决的问题包括但不限于：
1. 区间最小值、最大值查询
2. 区间和、区间平均值查询
3. 区间内的特定元素查询
4. 区间元素更新（如修改某个区间内的元素值）
5. 区间内元素的增加或减少（如增加或减少区间内所有元素的值）

那么怎样才是一个线段树呢，首先我们从线段树的结点的结构引入

struct node
{
    int l;//结点的左端点下标
    int r;//结点的右端点下标
    int sum;//这个结点整个线段的和
}tree[MAXN*4];//开四倍叶子结点的个数的空间

我们来讨论一下线段树，所谓线段树，比如说，我们要求1~8的和，那么我们就可以用1~4的和和5~8的和来求，要求1~4的和，就要求1~2的和和3~4的和，依次类推，这就是线段树

然后我们还可以的到一个性质：节点 i ii的权值 = == 她的左儿子权值 + ++ 她的右儿子权值。因为 1 ∼ 4 1\sim 41∼4 的和就是等于 1 ∼ 2 1\sim 21∼2 的和与 2 ∼ 3 2\sim 32∼3 的和的和。

根据这个思路，我们就可以建树了，我们设一个结构体 tree，tree[i].l 与 tree[i].r 分别表示这个点代表的线段的左右下标，tree[i].sum 表示这个节点表示的线段和。

tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;

建树的代码：

void build(int i,int l,int r)//i表示树的结点，l是树的左边界，r是树的右边界
{
	tree[i].l=l;
	tree[i].r=r;
	if(l==r)//说明到了叶子结点
	{
		tree[i].sum=num[l];
		return ;
	}
	int mid=(l+r)/2;
	build(i*2,l,mid);//构建左子树
	build(i*2+1,mid+1,r);//构建右子树
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//回退算出权值
	return ;
}

简单的线段树（没有懒标记）

1.单点修改，区间查询

如何去实现单点修改这个操作呢？

我们需要去判断要修改的这个目标点dis在线段树的左子树还是右子树，然后一直判断，一直到最终子树的L==R时就说明找到了这个目标点，然后给目标点的权值加上K，然后回退一步步去修改路径上的值

void add(int i,int dis,int k)//往那边走，给哪边加上 
{
	if(tree[i].l==tree[i].r)//找到目标点
	{
		tree[i].sum+=k;
	}
	int mid=(tree[i].l+tree[i].r)/2;
	if(mid>=dis)//目标点在左子树
	{
		add(2*i,dis,k);
	}
	else//目标点在右子树
	{
		add(2*i+1,dis,k);
	}
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//回退求和
	return ;
}

如何去实现区间查询这个操作

还是对应上面那个图，加入我们有一个1~8的线段，我们想求1~3的权值和（可能例子很简单，让你无法感受到线段树的优势，但是如果换成1~1000中去求88~999的和，线段树的好处就显而易见了）

要求1~3的和，我们先看左子树（1~4）和区间1~3有交集，我们1~4的左子树1~2被完全包含在1~3这个区间，因而可以直接返回我们1~2区间的sum，然后1~4的右子树也和1~3有交集，因而需要将3~4这个线段分成3~3的左子树和4~4的右子树，加上3~3的左子树，我们的1~8的右子树（5~8）和1~3区间完全没有关系，因而可以直接返回一个0。

因此我们可以推出区间查询的方法：

如果这个区间被完全包括在目标区间里面，直接返回这个区间的值

如果这个区间和目标区间没有交集要直接返回0

如果这个区间的左子树和目标区间有交集，那么搜索左子树

如果这个区间的右子树和目标区间有交集，那么搜索右子树

int find(int i,int l,int r)

	if(tree[i].l>=l&&tree[i].r<=r)//标号为i的线段树被完全覆盖在目标区间里面
	{
		return tree[i].sum;//直接返回整个区间的和
	}
	if(tree[i].l>r||tree[i].r<l)//如果标号为i的的线段和目标区间没有交集，直接返回0
	return 0;
	int sum=0;
	int mid=(tree[i].l+tree[i].r)/2;//找到左子树的右边界，右子树的左边界为mid+1
	if(mid>=l)//如果左子树和目标区间有交集
	{
		sum+=find(i*2,l,r);
	}
	if(mid+1<=r)//如果右子树和目标区间有交集
	{
		sum+=find(i*2+1,l,r);
	}
	return sum;
}

2.区间修改，单点查询

思路就变为：如果把这个区间加上k ，相当于把这个区间涂上一个 k 的标记，然后单点查询的时候，就从上跑到下，把沿路的标记加起来就好。

这里面给区间贴标记的方式与上面的区间查找类似，原则还是那四条，只不过第一条：如果这个区间被完全包括在目标区间里面，直接返回这个区间的值变为了如果这个区间如果这个区间被完全包括在目标区间里面，将这个区间标记 k

如何去实现区间修改这个操作

实现区间修改的时候，我们在建树的时候不必回退求出每一个线段和，而是说只需要给叶子结点记录值即可

建树代码：

void build(int i,int l,int r)//i表示树的结点，l是树的左边界，r是树的右边界
{
	tree[i].l=l;
	tree[i].r=r;
	if(l==r)//说明到了叶子结点
	{
		tree[i].sum=num[l];
		return ;
	}
	int mid=(l+r)/2;
	build(i*2,l,mid);//构建左子树
	build(i*2+1,mid+1,r);//构建右子树
	return ;
}

然后我们在区间修改的时候给每一个被包含在目标区间的线段结点的sum加上修改值k，然后直接结束搜索即可，如果左子树和目标区间有交集，就递归去寻找左子树的线段，右子树和目标区间有交集就去寻找右子树，直到将属于目标区间的线段先加上一个k的标记

区间修改代码：

void add(int i,int l,int r,int k)
{
	if(tree[i].l>=l&&tree[i].r<=r)//结点i被包含在区间里面
	{
		tree[i].sum+=k;//给线段打上一个k的标记
		return;
	}
	int mid=(tree[i].l+tree[i].r)/2;//求出左子树的右边界，mid+1为右子树的左边界
	if(mid>=l)//如果左子树和目标区间有交集
	{
		add(2*i,l,r,k);
	}
	if(mid+1<=r)//右子树和目标区间有交集
	{
		add(2*i+1,l,r,k);
	}
	return ;
}

如何去实现单点查询这个操作

我们在查一个点的时候，直接从上跑到下，然后将路上的标记加起来，最后加上叶子结点的值就是最终单点的值

单点查询代码：

void find(int i,int dis)
{
	sum+=tree[i].sum;
	if(tree[i].l==tree[i].r)
	return ;
	int mid=(tree[i].l+tree[i].r);
	if(dis<=mid)
	{
		find(i*2,dis);
	}
	if(dis>=mid+1)
	{
		find(i*2+1,dis);
	}
}

复杂线段树（有懒标记）

1.区间修改，区间查询

当然了，有些人可能会认为，这个不就是之前那两个结合一下不就好了，这有什么难的，但是其实结果并不是这样

比如说：我们给区间1~3的区间加上了一个k的值，然后我们要求2~4这个区间，按照之前的操作来说，我们会给1~2进行标记，3~3进行标记，然后我们查询的时候查的是2~2和3~4的和，恰好都没有加上修改的值，因而，这种做法是错的，我们的正确做法，应该是用懒标记推下去（pushdown函数），去修改其结点的值

pushdown函数代码：

就是把自己的懒标记归零，并给自己的儿子加上，并让自己的儿子加上k*(r-l+1)

void pushdown(int i)
{
	if(tree[i].lz!=0)//如果父节点的的懒标记不为0
	{
		tree[i*2].lz+=tree[i].lz;//两个子树继承父节点的懒标记
		tree[i*2+1].lz+=tree[i].lz;
		int mid=(tree[i].l+tree[i].r)/2;//求出两个树的分界处
		tree[i*2]+=tree[i].lz+(mid-tree[i*2].l+1);//求出左子树的sum要加上的值
		tree[i*2+1]+=tree[i].lz+(tree[i*2+1].r-mid);//右子树的sum要加上的值
		tree[i].lz=0;//父节点懒标记要归0
	}
}

区间修改：线段被目标区间完全覆盖的时候时候要直接加上 k*区间长度，然后给那个线段的懒标记+k为了推给子树，然后return，如果没有完全覆盖，则调用pushdown函数，将这颗子树的懒标记推给子树，计算出子树的权值，然后判断左、右子树是否与目标区间有关，然后进行递归区间修改，然后同时进行回退求出计算的每个线段的权值

void add(int i,int l,int r,int k)
{
	if(tree[i].l>=l&&tree[i].r<=r)//线段被目标区间完全覆盖
	{
		tree[i].sum+=k*(tree[i].r-tree[i].l+1);//将这个区间的权值加上k*目标区间
		tree[i].lz+=k;//懒标记+k
		return;
	}
	pushdown(i);
	int mid=(tree[i].l+tree[i].r)/2;
	if(l<=mid)//如果左子树和目标区间有交集
	{
		add(i*2,l,r,k);
	}
	if(r>=mid+1)//右子树和目标区间有交集
	{
		add(i*2+1,l,r,k);
	}
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//回退求和 
	return;
}

区间查询：如果线段的范围在这个目标区间内，那返回这个目标区间的值，如果不在，则直接返回0，然后如果不属于上面两种情况，则先将懒标记推下去，然后判断左右子树是否和目标区间有关系，左子树和目标区间有关系则去递归左子树，右子树和目标区间有关系则去递归右子树，最后直接返回ans即可

int find(int i,int l,int r)
{
	if(tree[i].l>=l&&tree[i].r<=r)//被完全包含在目标区间
	{
		return tree[i].sum;
	}
	if(tree[i].r<l||tree[i].l>r)//与目标区间完全没有关系
	return 0;
	pushdown(i);//将懒标记推下去
	int sum=0;//记录查到的区间的和
	int mid=(tree[i].l+tree[i].r)/2;
	if(l<=mid)//左子树和目标区间有关系
	{
		sum+=find(i*2,l,r);
	}
	if(r>=mid+1)//右子树和目标区间有关系
	{
		sum+=find(i*2+1,l,r);
	}
	return sum;
}

2.乘法线段树

乘法线段树这个地方，首先要考虑的是先乘后加还是先加后乘，根据我们正常的数学逻辑来说，是先乘后加，事实结果也确实是先乘后加，但是为什么呢？

首先我们假设当前子节点的sum值为x，而父节点的乘法懒标记为m，加法懒标记为a，子节点的乘法懒标记为mul，加法懒标记为add

（1）按照先加后乘来计算

((x+add)*mul+a)*m

=(x+add+a/mul)*mul*m;

因此，子节点新的乘法懒标记为mul*m，这个没什么问题，而加法懒标记为add+a/mul，a/mul很明显会出现向下取整这种精度丢失的问题，因而说明先加后乘这种做法是错的

（2）按照先乘后加来计算

((x*mul)+add )*m+a

=x*(mul*m)+(add*m+a)

因此，子节点新的乘法懒标记为mul*m，这个没什么问题，而加法懒标记为add*m+a,也不存在精度丢失的问题，因而说明，先乘后加这种做法是对的

那么我们就要来先说明如何下推懒标记了，首先就是pushdown函数，我们在pushdown函数的时候首先两个子节点的值都会先乘父节点的乘法懒标记，然后加上父节点的加法懒标记*区间长度

然后我们在按照上面得到的结论，将左右子树的乘法和加法懒标记进行修改，最后将父节点的乘法懒标记变为1，加法懒标记变为0即可

pushdown函数代码：

void pushdown(int i)
{
	int x=tree[i].mul;
	int y=tree[i].add;
	tree[i*2].sum=(tree[i*2].sum*x+(y*(tree[i*2].r-tree[i*2].l+1))%mod)%mod;
	tree[i*2+1].sum=(tree[i*2+1].sum*x+y*(tree[i*2+1].r-tree[i*2+1].l+1))%mod;
	tree[i*2].mul=tree[i*2].mul*x%mod;
	tree[i*2].add=(tree[i*2].add*x+y)%mod;
	tree[i*2+1].mul=tree[i*2+1].mul*x%mod;
	tree[i*2+1].add=(tree[i*2+1].add*x+y)%mod;
	tree[i].mul=1;
	tree[i].add=0;
	return ;
}

PS：同时建树的时候也会有一些地方不一样，就是在建树的时候，同时也要将每个节点的乘法懒标记变为1

void build(int i,int l,int r)
{
	tree[i].l=l,tree[i].r=r;
	tree[i].mul=1;//每个节点的乘法懒标记都是1
	if(l==r)
	{
		tree[i].sum=num[l]%mod;
		return ;
	}
	int mid=(l+r)/2;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
	return ;
}

区间加的代码和上面的没什么不同

void add(int i,int l,int r,int k)
{
	if(tree[i].l>=l&&tree[i].r<=r)
	{
		tree[i].sum=(tree[i].sum+k*(tree[i].r-tree[i].l+1))%mod;
		tree[i].add=(tree[i].add+k)%mod;
		return ;
	}
	pushdown(i);
	int mid=(tree[i].l+tree[i].r)/2;
	if(mid>=l)
	{
		add(i*2,l,r,k);
	}
	if(mid+1<=r)
	{
		add(i*2+1,l,r,k);
	}
	tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
	return ;
}

区间乘的代码也是和加类似，只不过在乘的时候不只是改变乘法懒标记，还有加法懒标记

void mul(int i,int l,int r,int k)
{
	if(tree[i].l>=l&&tree[i].r<=r)
	{
		tree[i].sum=(tree[i].sum*k)%mod;
		tree[i].mul=(tree[i].mul*k)%mod;
		tree[i].add=(tree[i].add*k)%mod;
		return ;
	}
	pushdown(i);
	int mid=(tree[i].l+tree[i].r)/2;
	if(mid>=l)
	{
		mul(2*i,l,r,k);
	}
	if(mid+1<=r)
	{
		mul(2*i+1,l,r,k);
	}
	tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
	return ;
}

最后就是区间查找代码和上面可以说是一模一样

int find(int i,int l,int r)
{
	if(tree[i].l>=l&&tree[i].r<=r)
	{
		return tree[i].sum%mod;
	}
	if(tree[i].l>r||tree[i].r<l)
	return 0;
	pushdown(i);
	int sum=0;
	int mid=(tree[i].l+tree[i].r)/2;
	if(mid>=l)
	{
		sum=(sum+find(i*2,l,r))%mod;
	}
	if(mid+1<=r)
	{
		sum=(sum+find(i*2+1,l,r))%mod;
	}
	return sum;
}

相关例题：

1.单点修改，区间查询

P3374 【模板】树状数组 1

题意：就是说你有两种操作，一种是将某个数加上x，另一种是查询一个区间的和，很明显的单点修改，区间查询模版题

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int num[500005];
int flag;
int x,y;
struct node{
	int l;
	int r;
	int sum;
}tree[500005*4];
int sum;

void build(int i,int l,int r)
{
	tree[i].l=l,tree[i].r=r;
	if(l==r)
	{
		tree[i].sum=num[l];
		return ;
	}
	int mid=(l+r)/2;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
	return ;
}
 
void add(int i,int dis,int k)
{
	if(tree[i].l==tree[i].r)
	{
		tree[i].sum+=k;
		return ;
	}
	int mid=(tree[i].l+tree[i].r)/2;
	if(mid>=dis)
	{
		add(i*2,dis,k);
	}
	else
	{
		add(i*2+1,dis,k);
	}
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
	return;
}
 
int find(int i,int l,int r)
{
	if(tree[i].l>=l&&tree[i].r<=r)
	{
		return tree[i].sum;
	}
	int mid=(tree[i].l+tree[i].r)/2;
	int sum=0;
	if(l<=mid)
	{
		sum+=find(i*2,l,r);
	}
	if(mid+1<=r)
	{
		sum+=find(i*2+1,l,r);
	}
	return sum;
}
 
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>num[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		cin>>flag;
		if(flag==1)
		{
			cin>>x>>y;
			add(1,x,y);
		}
		else
		{
			cin>>x>>y;
			cout<<find(1,x,y)<<"\n";
		}
	}
	return 0;
}

2.区间修改，单点查询

P3368 【模板】树状数组 2

题意：给你一个区间，给区间上的每一个数都加上一个x或者给你一个数，要你求那个数在修改后的值为多少，很明显的区间修改，单点查询问题

#include<bits/stdc++.h>
using namespace std;
#define int long long

int n,m;
int a1[500005];
int flag;
int a,b,c;
int sum;
struct node
{
    int l;
    int r;
    int sum;
}tree[500005*4];

void build(int i,int l,int r)
{
    tree[i].l=l;
    tree[i].r=r; 
    if(l==r)
    {
        tree[i].sum=a1[l]; 
        return ;
    }
    int mid=(l+r)/2;
    build(2*i,l,mid);
    build(2*i+1,mid+1,r);
    return ;
}

void add(int i,int l,int r,int k)
{
    if(tree[i].l>=l && tree[i].r<=r)
    {
        tree[i].sum+=k;
        return ;
    }
    int mid=(tree[i].l+tree[i].r)/2; 
    if(l<=mid)
    {
        add(2*i,l,r,k);
    }
    if(r>mid)
    {
        add(2*i+1,l,r,k);
    }
    return ;
}

void find(int i,int x)
{
    sum+=tree[i].sum;
    if(tree[i].l==tree[i].r)
    {
        return ;
    }
    int mid=(tree[i].l+tree[i].r)/2;
    if(x<=mid)
    {
        find(2*i,x);
    }
    else
    {
        find(2*i+1,x);
    }
    return ;
}

signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a1[i];
    }
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        cin>>flag;
        if(flag==1)
        {
            cin>>a>>b>>c;
            add(1,a,b,c);
        }
        else
        {
            cin>>a;
            sum = 0; 
            find(1,a);
            cout<<sum<<"\n";
        }
    }
    return 0;
}

3.区间修改，区间查询

P3372 【模板】线段树 1

题意：还是两种操作，一种是给区间每一个数加上一个k，另一个操作是去看区间内的每一个数的和，经典的区间修改，区间查询问题

#include<bits/stdc++.h>
using namespace std;
#define int long long

int n,m;
int num[100005];
int flag;
int x,y,z;
struct node{
	int l;
	int r;
	int sum;
	int lz;
}tree[100005*4];


void build(int i,int l,int r)
{
	tree[i].l=l,tree[i].r=r;
	if(l==r)
	{
		tree[i].sum=num[l];
		return ;
	}
	int mid=(l+r)/2;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
	return ;
}
 
void pushdown(int i)
{
	if(tree[i].lz!=0)
	{
		tree[i*2].lz+=tree[i].lz;
		tree[i*2+1].lz+=tree[i].lz;
		int mid=(tree[i].l+tree[i].r)/2;
		tree[i*2].sum+=tree[i].lz*(mid-tree[i].l+1);
		tree[i*2+1].sum+=tree[i].lz*(tree[i].r-mid);
		tree[i].lz=0;
	}
	return ;
}
 
void add(int i,int l,int r,int k)
{
	if(tree[i].l>=l&&tree[i].r<=r)
	{
		tree[i].sum+=k*(tree[i].r-tree[i].l+1);
		tree[i].lz+=k;
		return ;
	}
	pushdown(i);
	int mid=(tree[i].l+tree[i].r)/2;
	if(mid>=l)
	{
		add(i*2,l,r,k);
	}
	if(mid+1<=r)
	{
		add(i*2+1,l,r,k);
	}
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
	return ;
}
 
int find(int i,int l,int r)
{
	if(tree[i].l>=l&&tree[i].r<=r)
	{
		return tree[i].sum;
	}
	if(tree[i].l>r&&tree[i].r<l)
	return 0;
	pushdown(i);
	int sum=0;
	int mid=(tree[i].l+tree[i].r)/2;
	if(mid>=l)
	{
		sum+=find(i*2,l,r);
	}
	if(r>=mid+1)
	{
		sum+=find(i*2+1,l,r);
	}
	return sum;
}
 
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>num[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		cin>>flag;
		if(flag==1)
		{
			cin>>x>>y>>z;
			add(1,x,y,z);
		}
		else
		{
			cin>>x>>y;
			cout<<find(1,x,y)<<"\n";
		}
	}
	return 0;
}

4.乘法线段树

P3373 【模板】线段树 2

题意：变成三种操作了，一种操作是将区间每一个数乘x，第二种操作是将区间每一个数加上x，第三种操作是求区间的一个和，经典的乘法线段树问题

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q,mod;
int num[100005];
int flag;
int a,b,c;
struct node{
	int l;
	int r;
	int sum;
	int mul;
	int add;
}tree[100005*4];

void build(int i,int l,int r)
{
	tree[i].l=l,tree[i].r=r;
	tree[i].mul=1;//第二处 
	if(l==r)
	{
		tree[i].sum=num[l]%mod;
		return ;//第三处 
	}
	int mid=(l+r)/2;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
	return ;
}

void pushdown(int i)
{
	int x=tree[i].mul;
	int y=tree[i].add;
	tree[i*2].sum=(tree[i*2].sum*x+(y*(tree[i*2].r-tree[i*2].l+1))%mod)%mod;
	tree[i*2+1].sum=(tree[i*2+1].sum*x+y*(tree[i*2+1].r-tree[i*2+1].l+1))%mod;
	tree[i*2].mul=tree[i*2].mul*x%mod;
	tree[i*2].add=(tree[i*2].add*x+y)%mod;
	tree[i*2+1].mul=tree[i*2+1].mul*x%mod;
	tree[i*2+1].add=(tree[i*2+1].add*x+y)%mod;
	tree[i].mul=1;
	tree[i].add=0;
	return ;
} 
 
void add(int i,int l,int r,int k)
{
	if(tree[i].l>=l&&tree[i].r<=r)
	{
		tree[i].sum=(tree[i].sum+k*(tree[i].r-tree[i].l+1))%mod;
		tree[i].add=(tree[i].add+k)%mod;
		return ;
	}
	pushdown(i);
	int mid=(tree[i].l+tree[i].r)/2;
	if(mid>=l)
	{
		add(i*2,l,r,k);
	}
	if(mid+1<=r)
	{
		add(i*2+1,l,r,k);
	}
	tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
	return ;
}
 
void mul(int i,int l,int r,int k)
{
	if(tree[i].l>=l&&tree[i].r<=r)
	{
		tree[i].sum=(tree[i].sum*k)%mod;
		tree[i].mul=(tree[i].mul*k)%mod;
		tree[i].add=(tree[i].add*k)%mod;
		return ;
	}
	pushdown(i);
	int mid=(tree[i].l+tree[i].r)/2;
	if(mid>=l)
	{
		mul(2*i,l,r,k);
	}
	if(mid+1<=r)
	{
		mul(2*i+1,l,r,k);
	}
	tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
	return ;
}
 
int find(int i,int l,int r)
{
	if(tree[i].l>=l&&tree[i].r<=r)
	{
		return tree[i].sum%mod;
	}
	if(tree[i].l>r||tree[i].r<l)
	return 0;
	pushdown(i);//第一处 
	int sum=0;
	int mid=(tree[i].l+tree[i].r)/2;
	if(mid>=l)
	{
		sum=(sum+find(i*2,l,r))%mod;
	}
	if(mid+1<=r)
	{
		sum=(sum+find(i*2+1,l,r))%mod;
	}
	return sum;
}
 
signed main()
{
	cin>>n>>q>>mod;
	for(int i=1;i<=n;i++)
	{
		cin>>num[i];
	}
	build(1,1,n);
	for(int i=1;i<=q;i++)
	{
		cin>>flag;
		if(flag==1)
		{
			cin>>a>>b>>c;
			mul(1,a,b,c);
		}
		if(flag==2)
		{
			cin>>a>>b>>c;
			add(1,a,b,c);
		}
		if(flag==3)
		{
			cin>>a>>b;
			cout<<find(1,a,b)%mod<<"\n";
		}
	}
	return 0;
}