对于一个数据结构而言，我们总要能对其进行两件事：修改和操作。操作在这里是一个专有名词，专门指代求最值、求和等操作，具体能指代什么操作之后再聊。
如果朴素的用数组进行存储，那么修改是O(1)的，而操作往往是O（n）的。
当操作指的是求和的时候，我们可以使用前缀和算法，前缀和使得操作是O(1)的，然而，前缀和同时也使得修改是O（n）的。
对于其他操作，也有类似于前缀和一样的较为简单的做法使得操作变成一个O（1）的过程，但他们却也同样会这的修改变成了一个O（n）的过程，我们讲包括前缀和本身在内的这些朴素优化方法统称为类前缀和做法。
如果我们要同时进行大量修改和操作，那么不管是朴素数组法还是类前缀和做法，总的时间复杂度都是O(n^2)的，那么有没有什么办法可以简化这一点呢？有的，线段树。线段树可以使得操作和修改都变成O(logn)的过程，虽然O（logn）比不过O（1），但是看总时间复杂度时，O(nlogn)相比于O（n^2）可谓是遥遥领先，这便是这一数据结构的优点。
至于树状数组，则是线段树的特化版，节约了75%的空间与90%的时间，牺牲了适用范围的结果，详见我的《树状数组》一文
这里继续介绍线段树
线段树的核心思想在于把原序列用递归式的二分法化成多个区间，从而形成一个二叉树，树的每个非叶子节点都对应着一个区间，叶节点则对应着原序列的特定元素。每一个节点代表着的是一个区间，存储的内容既包括区间的左右端点，还包括与这区间有关相关数据。比如如果操作指的是求和，那么存储的内容便是区间元素的和。
建树的过程相当于是在预处理信息,是一个O（n）的过程，单点修改和区间查询都是一个递归的O（logN）过程，，区间修改则由于懒惰标记的引入，也是一个O（logN）的过程，代码如下
const int MaxN=100000+5;
int a[MaxN],Nmax=-1;
struct node
{
int l,r,sum,add;
node(){l=r=sum=add=0;}
node(int L,int R,int SUM,int ADD){l=L;r=R;sum=SUM;add=ADD;}
}tr[MaxN*4];
//x是节点编号，根据完全二叉树的性质可知，x节点的左右子节点编号为x*2，x*2+1
void _build(int x,int l,int r)
{
tr[x].l=l,tr[x].r=r;//节点表示区间的左右界
if(l==r)
{
//若l=r，说明这个节点是叶子节点，直接赋值
tr[x].sum=a[l];//a是原数列
Nmax=max(Nmax,x);
return;
}
int mid=(l+r)/2;//mid表示左右子区间的间隔
_build(x<<1,l,mid),_build((x<<1)+1,mid+1,r);//递归建树
tr[x].sum=tr[x<<1].sum+tr[(x<<1)+1].sum;//pushup操作
}
inline void build(int r){_build(1,1,r);}
//区间查询
inline void pushdown(int now)
{
if(tr[now].add==0)return;
tr[now<<1].add+=tr[now].add,tr[(now<<1)+1].add+=tr[now].add;
tr[now<<1].sum+=tr[now].add*(tr[now<<1].r-tr[now<<1].l+1);
tr[(now<<1)+1].sum+=tr[now].add*(tr[(now<<1)+1].r-tr[(now<<1)+1].l+1);
tr[now].add=0;
}
int _query(int x,int l,int r)
{
if(tr[x].l>=l&&tr[x].r<=r) return tr[x].sum;//如果该节点的区间被要查找的区间包括了，那么就不用继续找了，直接返回改节点的值就行了
pushdown(x);
int mid=(tr[x].l+tr[x].r)>>1;
int sum=0;
if(l<=mid&&r>=tr[x].l) sum+=_query(x<<1,l,r);//如果当前节点在要查找区间左边界的右面，那么递归查找左子树
if(r>=mid+1&&l<=tr[x].r) sum+=_query((x<<1)+1,l,r);//如果当前节点在要查找区间右边界的左面，那么递归查找右子树
return sum;//由此得出了该区间的值，返回即可
}
inline int query(int l,int r){return _query(1,l,r);}
//单点修改
void _change(int now,int x,int k)
{
if(tr[now].l==tr[now].r){tr[now].sum=k;return;}
pushdown(x);
int mid=(tr[now].l+tr[now].r)>>1;
if(x<=mid)_change((now<<1),x,k);
else _change((now<<1)+1,x,k);
tr[now].sum=tr[now<<1].sum+tr[(now<<1)+1].sum;
}
inline void change(int x,int k){_change(1,x,k);}
//某节点被打了懒惰标记表示它本身修改了，但他的子节点尚未修改
void _update(int now,int l,int r,int k)
{
if(r<tr[now].l||l>tr[now].r)return;
if(l<=tr[now].l&&tr[now].r<=r)
{
//cout<<"update"<<tr[now].l<<tr[now].r<<endl;
tr[now].sum+=k*(tr[now].r-tr[now].l+1);//先修改这个区间
tr[now].add+=k;//然后给它打上懒标记
return;
}
pushdown(now);
int mid=(tr[now].l+tr[now].r)/2;
if(l<=mid&&r>=tr[now].l)_update(now<<1,l,r,k);
if(r>=mid+1&&l<=tr[now].r)_update((now<<1)+1,l,r,k);
tr[now].sum=tr[now<<1].sum+tr[(now<<1)+1].sum;
//如果是叶节点，标记会被下传到不会被访问到的虚空节点去，便相当于是消除标记了，因而无需单独特判叶节点
}
void update(int l,int r,int k){_update(1,l,r,k);}
View Code
TRANSLATE with
- 中文（简体）
- 中文（繁体）
- 丹麦语
- 乌克兰语
- 乌尔都语
- 亚美尼亚语
- 俄语
- 保加利亚语
- 克罗地亚语
- 冰岛语
- 加泰罗尼亚语
- 匈牙利语
- 卡纳达语
- 印地语
- 印尼语
- 古吉拉特语
- 哈萨克语
- 土耳其语
- 威尔士语
- 孟加拉语
- 尼泊尔语
- 布尔语(南非荷兰语)
- 希伯来语
- 希腊语
- 库尔德语
- 德语
- 意大利语
- 拉脱维亚语
- 挪威语
- 捷克语
- 斯洛伐克语
- 斯洛文尼亚语
- 旁遮普语
- 日语
- 普什图语
- 毛利语
- 法语
- 波兰语
- 波斯语
- 泰卢固语
- 泰米尔语
- 泰语
- 海地克里奥尔语
- 爱沙尼亚语
- 瑞典语
- 立陶宛语
- 缅甸语
- 罗马尼亚语
- 老挝语
- 芬兰语
- 英语
- 荷兰语
- 萨摩亚语
- 葡萄牙语
- 西班牙语
- 越南语
- 阿塞拜疆语
- 阿姆哈拉语
- 阿尔巴尼亚语
- 阿拉伯语
- 韩语
- 马尔加什语
- 马拉地语
- 马拉雅拉姆语
- 马来语
- 马耳他语
- 高棉语