通过做题目思考：为什么我们要学线段树呢？
下面的抛出两个问题一起思考一下：
问题1 ：
给1000个正整数，编号1到1000，用a[1],a[2],…,a[1000]表示。
统计：1.编号从L到R的所有数之和为多少？
其中1<= L <= R <= 1000.
你很快就可以思考出解决方法：
- O（n）枚举搜索
- 前缀和O(1)。
问题2：
给出n个数，n<=1000000，和m个操作，每个操作可能有两种：
- 在某个位置加上一个数；
- 询问区间[l，r]的和，并输出。
O（n）枚举。（超时呀！！！）那怎么办呢？
这个时候也思考一下之前认知里有的解决问题的方式----前缀和
你也会发现动态修改是不能用静态的前缀和实现的。
那我们通过思考，可以知道我们所学习的知识对有些问题是无法解决的时候。（学过线段树或者数组数组的除外）于是，我们就需要学习新的算法了。一种强大的数据结构：线段树（树状数组也是可以做这几个问题的）
好，接下来，我们开始一步一步走向线段树：
一.详细讲解线段树。
线段树的基础操作主要有5个：
建树、单点查询、单点修改、区间查询、区间修改。
线段树，是一种二叉搜索树。它将一段区间划分为若干单位区间，每一个节点都储存着一个区间。虽然说是一个区间，但实际它储存的是一个区间的信息（数值）。
线段树基础思想：分块？二分？各有看法，但实际用起来就是二分。
-
每个节点的左孩子区间范围为[l，mid]，右孩子为[mid+1,r]
-
对于结点k，左孩子结点为2k，右孩子为2k+1，这是完全二叉树性质。
如下图：
1.建树
建树的实现，思想就是分治，根本上也可以说是二分。
每个节点以结构体的方式存储（当然以后用数组比较好，节省代码量减少写代码的时间），结构体包含以下几个信息：
void pushup(int rt)//更新该节点维护的值,求和
{
MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}实现思路：
利用二分，从二叉树的根开始。
-
二分到每一个节点，给它左右端点确定范围。
-
如果是叶子节点，存储要维护的信息。（输入的初始数据。）
-
状态合并。将某个结点w的左右两个孩子值之和合并到w上。
可以看代码：
svoid build(int l,int r,int rt)//建立线段树
{
if(l==r)
{
scanf("%d",&MAX[rt]);
return;
}
int m=(l+r)/2;
build(l,m,rt*2);
build(m+1,r,2*rt+1);
pushup(rt);
}最后要注意：
-
结构体要开4倍空间，看上面画的一个[1,10]的线段树就懂了。
-
自己写的时候不要漏了return语句，因为到了叶子节点不需要再继续递归了。
2.单点查询
单点，就是一个点进行查询。因为线段树的特殊性，这里的点，就是左右端点相等的时候的 “区间”，也可以说是叶子节点。
方式：二分查询：
-
如果当前枚举的点左右端点相等，即叶子节点，就是目标节点。
-
如果不是，利用二分思想。对查询位置为x，和当前结点区间范围为 [l，r],中点为mid。如果x<=mid，则递归它的左孩子，否则递归它的右孩子，那么最后一定可以得出答案。
我们仍然需要证明一下其正确性：
假如不是目标位置，由if—else语句对目标位置定位，逐步缩小目标范围，最后一定能只到达目标叶子节点。
再详细一点：
我们二分的情况有三种：
void ask(int k)
{
if(tree[k].l==tree[k].r) //当前结点的左右端点相等，是叶子节点，这就是答案
{
ans=tree[k].w;
return ;
}
int mid=(tree[k].l+tree[k].r)/2;
if(x<=mid) ask(k*2);//目标位置比中点靠左，递归左孩子
else ask(k*2+1);//反之，递归右孩子
}3.单点修改
结合单点查询的原理，找到x的位置；根据建树状态合并的原理，修改每个结点的状态。
void update(int p,int sc,int l,int r,int rt)//单点更新
{
if(l==r)
{
MAX[rt]=sc;
return;
}
int m=(l+r)>>1;
if(p<=m)
update(p,sc,l,m,rt*2);
else
update(p,sc,m+1,r,2*rt+1);
pushup(rt);
}4.区间查询
mid=(l+r)/2；
y<=mid ,即 查询区间全在，当前区间的左子区间，往左孩子走
x>mid 即 查询区间全在，当前区间的右子区间，往右孩子走
否则，两个子区间都走
正确性分析
情况1，3不用说，对于情况2，最差情况是搜到叶子节点，此时一定满足情况1
int query(int L,int R,int l,int r,int rt)//要查询的区间和当前的左右节点和根节点
{
if(L<=l&&r<=R)//[l,r]∈[L,R]
{
return MAX[rt];
}
int m=(l+r)>>1;//找中间点
int ret=0;
if(L<=m) ret=max(ret,query(L,R,l,m,rt*2));
if(R>m) ret=max(ret,query(L,R,m+1,r,2*rt+1));
return ret;
}完整代码：
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define mod 10000007
#define debug() puts("what the ***!!!")
#define N 200200
#define M 1000000
#define ll long long
using namespace std;
//#define lson l,m,rt<<1
//#define rson m+1,r,rt<<1|1 //位运算，|可以理解为+
int MAX[4*N];
void pushup(int rt)//更新该节点维护的值,求和
{
MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}
void build(int l,int r,int rt)//建立线段树
{
if(l==r)
{
scanf("%d",&MAX[rt]);
return;
}
int m=(l+r)/2;
build(l,m,rt*2);
build(m+1,r,2*rt+1);
pushup(rt);
}
void update(int p,int sc,int l,int r,int rt)//单点更新
{
if(l==r)
{
MAX[rt]=sc;
return;
}
int m=(l+r)>>1;
if(p<=m)
update(p,sc,l,m,rt*2);
else
update(p,sc,m+1,r,2*rt+1);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt)//要查询的区间和当前的左右节点和根节点
{
if(L<=l&&r<=R)//[l,r]∈[L,R]
{
return MAX[rt];
}
int m=(l+r)>>1;//找中间点
int ret=0;
if(L<=m) ret=max(ret,query(L,R,l,m,rt*2));
if(R>m) ret=max(ret,query(L,R,m+1,r,2*rt+1));
return ret;
}
int main()
{
int n,m,a,b;
char s[5];
while(~scanf("%d%d",&n,&m))
{
mem(MAX,0);
build(1,n,1);
while(m--)
{
scanf("%s%d%d",s,&a,&b);
if(s[0]=='Q')
printf("%d\n",query(a,b,1,n,1));
if(s[0]=='U')
update(a,b,1,n,1);
}
}
return 0;
}
京公网安备 11010502036488号