线段树模板讲解

题目描述

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

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

输入格式

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

第二行包含 n 个用空格分隔的整数 ai​，其中第 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

输出 #2

11 8 20

首先我们明确：线段树的思想是使用一个下标之间有关数组模拟一棵树来储存原始数组中不同区间的值。

它使用二分法将区间分段，具体为：

1.定义初始化函数f(int l,int r,int i,int *a[])，分别表示：当前处理的原始数组区间左端、右端，线段树数组（tree）的索引（一般从1开始），原始数组

2.如果l=r，让tree[i]=a[l]

3.如果l != r，让区间中点mid=(l+r)/2，继续递归f(l,mid,i*2,a),f(mid,r,2*i+1,a)。其中，2*i是i的左儿子，2*i+1是右儿子。（这样计算下标可以连续，紧凑的使用tree中的空间）然后令tree[i]=tree[2*i+1]+tree[2*i]。(仅存值的情况下，如果有别的数据也是类似的形式，本题中还有区间左右端)

然后就是懒标记传递及区间加法。

补充一下，懒标记是防止查询算法的复杂度在特殊情况下退化成O(n)的，作用为：仅在需要向下查询时传递操作。

这里我定义：懒标记tag是我对当前tree节点对应的区间已经加上的值。于是有了下面的操作：(tag!=0，当前节点为i)

1.tree[2*i+1].sum+=当前区间长度* tree[i].tag,tree[2*i+1]同理。

2.tree[i].tag=0,清除当前节点的懒标记。

对于区间加法：（需要对[l,r]加k）

1.如果当前tree节点记录的区间左右端包含在加法区间[l,r]内，则节点值+=当前区间长度*k，tree[i].tag+=k。

2.如果不包含，则下传懒标记，继续访问左右儿子，并重新赋值tree[i].sum为左右儿子的和。

查询：（查[l,r]）

1.如果当前tree节点记录的区间左右端包含在区间[l,r]内,直接返回值。

2.如果不包含，则下传懒标记，继续访问左右儿子，并返回左右儿子的查找结果。

剩下的就是数组tree大小注意开成4*n，并且和的值需要使用long long。代码如下：

#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; int n,m; struct node{ int l,r; ull sum=0,tag=0; }; vector<node>tree(4e5+1); //初始化 void initial(vector<ull>&a,int l,int r,int site){ if(l!=r){ int mid=(l+r)/2; initial(a,l,mid,site*2); initial(a,mid+1,r,site*2+1); tree[site].sum=tree[site*2+1].sum+tree[site*2].sum; } else if(l==r) tree[site].sum=a[l]; tree[site].l=l; tree[site].r=r; } //重赋值 void push_up(int i){ tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum; } //懒标记传递 void passdown(int i){ if(tree[i].tag){ int rs=i*2+1,ls=2*i; tree[ls].sum+=(tree[ls].r-tree[ls].l+1)*tree[i].tag; tree[ls].tag+=tree[i].tag; tree[rs].sum+=(tree[rs].r-tree[rs].l+1)*tree[i].tag; tree[rs].tag+=tree[i].tag; tree[i].tag=0; } } //加法 void _plus(int i,int l,int r,ull k){ if(tree[i].l>=l&&tree[i].r<=r){ tree[i].sum+=(tree[i].r-tree[i].l+1)*k; tree[i].tag+=k; return ; } passdown(i); int mid=(tree[i].r+tree[i].l)/2; if(l<=mid) _plus(2*i,l,r,k); if(r>mid)_plus(2*i+1,l,r,k); push_up(i); } //查询 ull output(int l,int r,int i){ if(tree[i].l>=l&&tree[i].r<=r){ return tree[i].sum; } passdown(i); int mid=(tree[i].l+tree[i].r)/2; ull ans=0; if(l<=mid) ans+=output(l,r,2*i); if(r>mid) ans+=output(l,r,2*i+1); return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); cin>>n>>m; vector<ull>a(n+1); stringstream ss; for(int i=1;i<=n;i++){ cin>>a[i]; } initial(a,1,n,1); for(int i=0;i<m;i++){ int sw,r,l; ull k; cin>>sw; switch (sw) { case 1: cin>>l>>r>>k; _plus(1,l,r,k); break; case 2: cin>>l>>r; ss<<output(l,r,1)<<"\n"; break; } } cout<<ss.str(); return 0; }