引入

题目描述

给定\(n\)个数\(a[1],a[2],a[3]...a[n]\),现在又下面两种操作：
1.询问区间\([x,y]\)的和，并输出。
2.将下标为\(x\)的数增加\(val\)。
一共\(x\)此操作
\(1\le n,m\le 100000\)，保证在\(int\)范围内。

方法一：暴力枚举

定义数组\(a\)储存\(n\)个元素。
求区间和的时间复杂度为O(n),将\(a[x]\)增加\(val\)的时间复杂度为O(1)，总时间复杂度为O(nm)。
为什么超时？
因为每次求和的速度太慢了

前缀和

定义数组\(sum\)，表示前缀和
求区间和的时间复杂度为O(1)，将\(a[x]\)增加\(val\)的时间复杂度为O(n)。
因为每一次进行增加操作，就需要更新所有的前缀和，所以总的时间复杂度为O(mn)。

总结

所以，我们应该选取折中的方案

线段树

简介

将区间信息储存在树形结构中，也可以进行求解RMQ问题。
线段树解决了树状数组只能存储前缀信息和\(st\)表只能进行静态访问的问题。
线段树不光可以解决区间的前缀信息还可以求解区间的最值问题。
所以大部分可以用树状数组解决的问题都是可以用线段树解决的，但是这并不代表树状数组是没有意义的。
因为线段树的常数与码量较大，在有些时候并不是最优的选择。

基本思想

线段树其实本质上就是一棵完全二叉树，其根节点储存的就是原来的数据。
每个节点都有自己的左右端点，其中存储的数据就是答案。

单点修改线段树

以下代码求取的是区间最大值

建树

建树的操作使用了递归函数，传入的三个参数k、l和r分别表示现在的节点，节点所表示的左端点与右端点。
如果左右两个端点是一样的就表示这是一个叶子节点，可以直接赋值并返回。
否则利用完全二叉树的性质进行递归寻找吗叶子节点。
在递归操作结束后将这个节点的两个子节点的最大值取出进行比较，其中的最大值就是这个区间的最大值。

void build(int k,int l,int r) {
	if(l==r){
		s[k]=a[l];
		return;
	}int mid=(l+r)/2;
	build(2*k,l,mid);
	build(2*k+1,mid+1,r);
	s[k]=max(s[k*2],s[k*2+1]);
    return ;
}

修改

add函数传入的参数表示现在的节点是k，左端点与右端点分别是l与r。
需要将第x个点修改为val。

void add(int k,int l,int r,int x,int val) {
	if(l==r&&l==x){
		s[k]=val;
		return;
	}if(x<l||x>r)
		return;
	int mid=(l+r)/2;
	if(l<=x&&x<=mid)
		add(k*2,l,mid,x,val);
	if(mid+1<=x&&x<=r)
		add(k*2+1,mid+1,r,x,val);
	s[k]=max(s[k*2],s[k*2+1]);
    return ;
}

求最大值

sum函数传入的参数分别表示在第k个节点的左右端点分别为l和r。
求x到y这个区间中的最大值。

int sum(int k,int l,int r,int x,int y) {
	if(y<l||x>r)
		return 0;
	if(x<=l&&r<=y)
		return s[k];
	int mid=(l+r)/2;
	return max(sum(k*2,l,mid,x,y),sum(k*2+1,mid+1,r,x,y));
}

区间修改

区间修改的代码与单点修改大同小异，只是新增了一个lazy数组以提高时间复杂度
lazy数组完成的工作就是懒惰加载，只将需要访问的部分进行更改

处理lazy数组

void updata(ll k,ll lleft,ll rright){
	if(lazy[k]){
		lazy[k*2]+=lazy[k];
		lazy[k*2+1]+=lazy[k];
		ll mid=(lleft+rright-1)/2;
		s[k*2]+=lazy[k]*(mid-lleft+1);
		s[k*2+1]+=lazy[k]*(rright-mid);
		lazy[k]=0;
	}return ;
}

进行区间修改

void make(ll lleft,ll rright,ll l,ll r,ll val,ll x){
	if(l==lleft&&r==rright) {
		lazy[x]+=val;
		s[x]+=val*(r-l+1);
		return ;
	}if(l==r)
		return ;
	updata(x,l,r);
	ll mid=(l+r-1)>>1;
	if(rright<=mid)
		make(lleft,rright,l,mid,val,x<<1);
	else{
		if(lleft>mid)
			make(lleft,rright,mid+1,r,val,x*2+1);
		else{
			make(lleft,mid,l,mid,val,x*2);
			make(mid+1,rright,mid+1,r,val,x*2+1);
		}
	}s[x]=s[x<<1]+s[x*2+1];
	return ;
}

建树

void build(ll lleft,ll rright,ll x){
	if(lleft==rright){
		s[x]=a[lleft];
		return ;
	}ll mid=(lleft+rright-1)/2;
	build(lleft,mid,x*2);
	build(mid+1,rright,x*2+1);
	s[x]=s[x*2]+s[x*2+1];
	return ;
}

求区间和

ll sum(ll lleft,ll rright,ll l,ll r,ll k){
	if(lleft==l&&rright==r)
		return s[k];
	updata(k,l,r);
	ll mid=(l+r-1)/2;
	if(rright<=mid)
		return sum(lleft,rright,l,mid,k*2);
	if(lleft>mid)
		return sum(lleft,rright,mid+1,r,k*2+1);
	return sum(lleft,mid,l,mid,k*2)+sum(mid+1,rright,mid+1,r,k*2+1);
}