2个部分介绍一下线段树思想及简单用法：
1、引入概念
2、区间查询/修改与单点修改/查询
引入概念
百度定义是这样的：将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界。
简单地说，线段树就是一个二叉树，每个结点记录的都是一段区间的信息，可以快速进行对指定区间的修改和查询，时间复杂度为O(logN)。
比如a[4]={1,4,3,2}线段树如下图：
可以从图中看到，父亲节点的权值等于左孩子的权值加右孩子的权值，也就是tree[i].sum=tree[2*i].sum+tree[2*i+1].sum，叶子结点就是我们输入的数据，且每个结点还需要记录它们的左右边界。
首先是定义的结构体：
#define ll long long
#define mod 998244353
const int MAXN=1e5+5, inf=1e9;
struct Tree
{
int l,r; //左边界和右边界的值
ll sum; //该区间的权值和
}tree[4*MAXN];
int ans[MAXN]; //输入n个数，for(i=1;i
下面是建树代码：
解释一下，调用build时不可以写build(0,0,n-1)，如果第一个结点信息tree[0]里，那根据上述，左孩子2*i依旧是0，所以第一个结点应该存在tree[1]里。
void build(int i,int l,int r) //调用build(1,1,n)
{
tree[i].l=l; //左边界
tree[i].r=r; //右边界
if(l==r)
{
tree[i].sum=ans[l]; //叶子结点
return ;
}
int mid=(l+r)>>1;
build(i*2,l,mid); //建立左子树
build(i*2+1,mid+1,r); //建立右子树
tree[i].sum=tree[i*2].sum+tree[i*2+1].sum; //父亲结点的权值等于左孩子权值加右孩子权值
}
区间查询/修改与单点修改/查询
线段树最简单的两种用法：
1、区间查询+单点修改
2、区间修改＋单点查询
1、区间查询＋单点修改
区间查询：
我们已经了解，每个结点都是一段区间的信息，现在我想计算出a[2]~a[4]的和，朴素算法就是循环暴力，显然，这非常消耗时间。
模拟一下线段树计算的过程，从根节点（tree[1]）开始查找，注意看图片红色字部分：
总结一下：
a、如果当前结点是查询区间的子集，那么就不需要往下找；
b、如果当前结点和查询区间无关，直接pass；
c、直接返回这个结点的权值，如果当前结点的左孩子和查询的区间有交集，那么就去找左孩子；
d、如果当前结点的右孩子和查询的区间有交集，那么就去找右孩子。
代码如下：
ll search1(int i,int x,int y) //区间查询
{
if(tree[i].l>=x&&tree[i].r
return tree[i].sum;
if(tree[i].l>y||tree[i].r return 0; ll s=0; if(tree[2*i].r>=x) //对应c s+=search1(2*i,x,y); if(tree[2*i+1].l s+=search1(2*i+1,x,y); return s; } 单点修改： 没错，还是这个图，它将贯彻整篇文章，将a[4]改成8，模拟一下查找过程： 一直向下查找，查找到叶子结点，修改叶子结点的值，然后向上回溯，修改每一个父亲结点的值，修改到根节点为止。 代码如下： void change(int i,int x,int k) //单点修改 { if(tree[i].l==tree[i].r&&tree[i].l==x) //找到叶子结点并修改 { tree[i].sum=k; return ; } if(tree[2*i].r>=x) //向左孩子寻找 change(2*i,x,k); if(tree[2*i+1].l change(2*i+1,x,k); tree[i].sum=tree[2*i].sum+tree[2*i+1].sum; //回溯，修改父亲结点的sum } 2、区间修改＋单点查询 区间修改： 同时给一段区间的每个数都加上一个值，这就是区间修改的一种。 现在可能会有一些疑惑，为什么区间修改不能和区间查询在一起，这个要更加复杂一些，为了便于理解，我们先介绍这两种简单的用法。 在区间修改里，结构体中的sum 不再存储权值，而是起一个标记的作用，上图： 现在模拟a[1]~a[3]全部加5的过程，思想和区间查询是一样的： 现在已经修改完毕了，可能你现在对这种修改方式比较疑惑，看完单点查询就理解了： 我们设一个变量t，存储的是我要查询的点的值。 模拟查询a[2]的过程： 有没有一种豁然开朗的感觉。 void sub(int i,int x,int y,int k) //区间修改 ，下面4个if和区间修改思想相同，不做解释 { if(tree[i].l>=x&&tree[i].r { tree[i].sum+=k; return ; } if(tree[i].l>y||tree[i].r return ; if(tree[2*i].r>=x) sub(2*i,x,y,k); if(tree[2*i+1].l sub(2*i+1,x,y,k); } void search2(int i,int x) //单点查询 { t+=tree[i].sum; if(tree[i].l==tree[i].r) //找到叶子结点停止 return ; if(tree[2*i].r>=x) //向左孩子寻找 search2(2*i,x); if(tree[2*i+1].l search2(2*i+1,x); } 关于线段树的进阶部分，下一篇文章再详细解释。
本文来自投稿，不代表本人立场，如若转载，请注明出处：http://www.sosokankan.com/article/2323938.html