线段树小解及模板

关于线段树，百度一下有很多教程，里面的图也很形象，作为一个刚入门几天的萌新，不打算班门弄斧，仅就这两天肝题的经验，写一个比较基础的模板。

这里先推荐一篇文库里比较好的文章，基本上吧线段树的很多方面都讲到了，照着里面的思路学会受益匪浅。

正文开始

首先，一个线段树一般有以下基本结构（以区间求和、更新为例）

struct segment_tree { int left,right; //当前位置线段树的左、右边界 int sum; //线段树功能处理变量，对于具体问题可进行相应修改 };

当然，在网路上绝大多数的题解、模板（包括我推荐的那篇文章）中是找不到这种东西的，原因是它太耗内存，如果你的数据量是100000，那你就需要100000 * 4 * 2 * 4 = 3200k来存你所创建的线段树的边界条件，占用了相当一步的内存，（实际应用时由于递归的参数调用不会节省这么多，但总还是会省一点，同时，网上的方法一般会直接用多个数组去代替结构体，原因大概也和内存占用有关，这里涉及到结构体内存的计算方法，就不详述了，如果非要用结构体实现一些功能（如离散化中的排序），并且需要优化内存的话，可以参考相关资料），但这样写法的好处是容易理解，对于初学者或者接触过面向对象编程的人来说更容易上手，如果你只是想要了解一下线段树的应用，用这种方法也不错，如果是冲着竞赛去的，那还是要用网上通用的那种方法。

网上通用的这种方法，其实是将原有结构中的left,right两个变量，变成了，l,r 两个参数，跟随函数的递归调用进行改变，所以，我们可以看到，网络上的大部分代码的头几行，必出现如下定义

#define lson rt << 1, l , m #define rson rt << 1 | 1 , m + 1 , r

用通俗的话翻译来说，这个替换文本中的内容就代表了一个节点的左（右）儿子的节点下标、区间左、右边界，代替了原有结构中的left,right，这样，将会相对减少内存。

然后我们来说一下线段树的基本操作模板（这里会分把两种写法的模板都做出来），其具体功能定义如下

结构体方法：

#define lson x << 1 //左儿子根节点 #define rson x << 1 | 1 //右儿子根节点 #define MAXN 100000 //数据量上限 struct segment_tree { int left,right; //当前位置线段树的左、右边界 int sum; //线段树功能处理变量 int add; //延迟用标记（单点更新时不需要） }; struct segment_tree rt[(MAXN << 1) + 3];

竞赛用方法：

#define lson x << 1, l, mid //左儿子根节点 #define rson x << 1 | 1, mid + 1, r //右儿子根节点 #define lt x << 1 #define rt x << 1 | 1 #define MAXN 100000 //数据量上限 int sum[(MAXN << 1) + 3]; //与结构体相同，根据具体功能定义数组 int add[(MAXN << 1) + 3];

首先是两个子功能函数

PushUp()

一般情况下，只要线段树涉及到建立、更新更新，就会用到PushUp函数，它其实只是一个子函数，主要实现的功能是根据标号为x的节点的左右子节点得到该节点（更新后）的元素值，因而根据不同的题目要求，PushUp的内容各不相同，是实际应用中改动最大的部分

结构体方法：

void PushUp(int x) { rt[x].sum = rt[lson].sum + rt[rson].sum; }竞赛用方法：

void PushUp(int x) { sum[x] = sum[lt] + sum[rt]; }

PushDown()

与PushUp不同，PushDown仅用于区间更新（即有延迟标记时）才会存在，主要作用是通过标号为x的节点，更新其两个子节点的相关元素值，并把其标记值“加”到子节点的延迟标记中（注意这里一般来说是“加”而不是赋值，添加的时候，方法也有可能不同），主要应用于含有区域更新的update，query函数中

结构体方法：

void PushDown(int x) { if(rt[x].add != 0) { rt[lson].add += rt[x].add; rt[rson].add += rt[x].add; rt[lson].sum += (rt[lson].right - rt[lson].left + 1) * rt[x].add; rt[rson].sum += (rt[rson].right - rt[rson].left + 1) * rt[x].add; rt[x].add = 0; } }竞赛用方法：

void PushDown(int x,int m) { if(add[x] != 0) { add[lt] += add[x]; add[rt] += add[x]; sum[lt] += (m - (m >> 1)) * add[x]; sum[rt] += (m >> 1) * add[x]; add[x] = 0; } }

Build()

该函数主要用于生成所需的功能线段树，（即初始化线段树），在主要在if(l == r)的部分根据不同的初值需要会有所更改；另，若所建立线段树初值全为某一定值，在第二种方法中，可省略build函数，改用memset函数对数组赋值即可。

结构体方法：

void build(int x, int L, int R) { rt[x].left = L; rt[x].right = R; rt[x].add = 0; if(L == R) { scanf("%d",&rt[x].sum); return; } int mid = (L + R) >> 1; build(lson, L, mid); build(rson, mid + 1, R); PushUp(x); } 竞赛用方法：

void build(int x, int l, int r) { add[x] = 0; if(l == r) { scanf("%d",sum[x]); return ; } int mid = (l + r) >> 1; build(lson); build(rson); PushUp(x); } update() 将所需要的点（区域改成相应的值或加上相应的值） 单点更新 该情况下不需要延迟标记，找到点，更改其值即可（这就是一个二分查找，不断逼近的过程）

结构体方法：

void update(int x, int pos, int val) { if(rt[x].left == rt[x].right) { rt[x].sum += val; return; } int mid = (rt[x].left + rt[x].right) >> 1; if(pos <= mid) update(lson, pos, val); else update(rson, pos, val); PushUp(x); } 竞赛用方法：

void update(int x, int l, int r, int pos, int val) { if(l == r) { sum[x] += val; return; } int mid = (l + r) >> 1; if(pos <= mid) update(lson, pos, val); else update(rson, pos, val); PushUp(x); } 区域更新 这里需要用到延迟标记，有了延迟标记后，只要该节点区间在所更改的区间内，即可段相关元素值进行修改操作，然后返回，这样，我们只需更新[L，R]之间的所有最大子区间即可完成更新，而不需要更新到最底层，这样大大提高了效率，但由于用到延迟标记，当我们想下两个子节点递归扩展调用时，就必须用PushDown函数对下一层的值进行更新（其实就是将其变为实际值）

结构体方法：

void update(int x, int L,int R,int val) { if(L <= rt[x].left && R >= rt[x].right) { rt[x].add += val; rt[x].sum += (rt[x].right - rt[x].left + 1) * val; return; } PushDown(x); int mid = (rt[x].left + rt[x].right) >> 1; if(L <= mid) update(lson, L, R, val); if(R > mid) update(rson, L, R, val); PushUp(x); } 竞赛用方法：

void update(int x, int l, int r, int L,int R,int val) { if(L <= l && R >= r) { add[x] += val; sum[x] += (r - l + 1) * val; return; } PushDown(x, r - l + 1); int mid = (l + r) >> 1; if(L <= mid) update(lson, L, R, val); if(R > mid) update(rson, L, R, val); PushUp(x); } query() 与update函数相同，在有延迟标记的情况下，需在下一次调用时进行PushDown操作 值得注意的是，进行区间查找时，注意区域结果的合成（在有的情况下，并不能直接调用线段树中的相关元素进行区域合成）

结构体方法：

int query(int x, int L, int R) { if(L <= rt[x].left && R >= rt[x].right) { return rt[x].sum; } PushDown(x); int mid = (rt[x].left + rt[x].right) >> 1; if(R <= mid) return query(lson, L, R); else if(L > mid) return query(rson, L, R); else return query(lson,L,R) + query(rson,L,R);  }竞赛用方法：

int query(int x,int l, int r, int L, int R) { if(L <= l && R >= r) { return sum[x]; } PushDown(x,r - l + 1); int mid = (l + r) >> 1; if(R <= mid) return query(lson, L, R); else if(L > mid) return query(rson, L, R); else return query(lson, L, R) + query(rson, L, R);  }

代码集总：

结构体方法：

#include <iostream> #define lson x << 1 //左儿子根节点 #define rson x << 1 | 1 //右儿子根节点 #define MAXN 100000 //数据量上限 struct segment_tree { int left,right; //当前位置线段树的左、右边界 int sum; //线段树功能处理变量 int add; //延迟用标记（单点更新时不需要） }; struct segment_tree rt[(MAXN << 1) + 3]; void PushUp(int x) { rt[x].sum = rt[lson].sum + rt[rson].sum; } void PushDown(int x) { if(rt[x].add != 0) { rt[lson].add += rt[x].add; rt[rson].add += rt[x].add; rt[lson].sum += (rt[lson].right - rt[lson].left + 1) * rt[x].add; rt[rson].sum += (rt[rson].right - rt[rson].left + 1) * rt[x].add; rt[x].add = 0; } } void build(int x, int L, int R) { rt[x].left = L; rt[x].right = R; rt[x].add = 0; if(L == R) { scanf("%d",&rt[x].sum); return; } int mid = (L + R) >> 1; build(lson, L, mid); build(rson, mid + 1, R); PushUp(x); } //单点更新 void update(int x, int pos, int val) { if(rt[x].left == rt[x].right) { rt[x].sum += val; return; } int mid = (rt[x].left + rt[x].right) >> 1; if(pos <= mid) update(lson, pos, val); else update(rson, pos, val); PushUp(x); } //区域更新 void update(int x, int L,int R,int val) { if(L <= rt[x].left && R >= rt[x].right) { rt[x].add += val; rt[x].sum += (rt[x].right - rt[x].left + 1) * val; return; } PushDown(x); int mid = (rt[x].left + rt[x].right) >> 1; if(L <= mid) update(lson, L, R, val); if(R > mid) update(rson, L, R, val); PushUp(x); } int query(int x, int L, int R) { if(L <= rt[x].left && R >= rt[x].right) { return rt[x].sum; } PushDown(x); int mid = (rt[x].left + rt[x].right) >> 1; if(R <= mid) return query(lson, L, R); else if(L > mid) return query(rson, L, R); else return query(lson,L,R) + query(rson,L,R);  }竞赛用方法：

#include <iostream> #define lson x << 1, l, mid //左儿子根节点 #define rson x << 1 | 1, mid + 1, r //右儿子根节点 #define lt x << 1 #define rt x << 1 | 1 #define MAXN 100000 //数据量上限 int sum[(MAXN << 1) + 3]; //与结构体相同，根据具体功能定义数组 int add[(MAXN << 1) + 3]; void PushUp(int x) { sum[x] = sum[lt] + sum[rt]; } void PushDown(int x,int m) { if(add[x] != 0) { add[lt] += add[x]; add[rt] += add[x]; sum[lt] += (m - (m >> 1)) * add[x]; sum[rt] += (m >> 1) * add[x]; add[x] = 0; } } void build(int x, int l, int r) { add[x] = 0; if(l == r) { scanf("%d",sum[x]); return ; } int mid = (l + r) >> 1; build(lson); build(rson); PushUp(x); } //单点更新 void update(int x, int l, int r, int pos, int val) { if(l == r) { sum[x] += val; return; } int mid = (l + r) >> 1; if(pos <= mid) update(lson, pos, val); else update(rson, pos, val); PushUp(x); } //区域更新 void update(int x, int l, int r, int L,int R,int val) { if(L <= l && R >= r) { add[x] += val; sum[x] += (r - l + 1) * val; return; } PushDown(x, r - l + 1); int mid = (l + r) >> 1; if(L <= mid) update(lson, L, R, val); if(R > mid) update(rson, L, R, val); PushUp(x); } int query(int x,int l, int r, int L, int R) { if(L <= l && R >= r) { return sum[x]; } PushDown(x,r - l + 1); int mid = (l + r) >> 1; if(R <= mid) return query(lson, L, R); else if(L > mid) return query(rson, L, R); else return query(lson, L, R) + query(rson, L, R);  } 【END】