以下只是自己对于线段树的看法：
线段树大约是用来快速对区间进行加减和求和，并快速查询值的操作。
但是，使用前提是这个操作必须可以分治，即a[i,j]=check(a[i,mid]，a[mid+1,j])
浅谈几个其中思想 很浅很浅的浅谈
0、递归建树中，放在递归操作之后的操作代表着让程序自底向上进行的操作；放在递归之前的代表着让程序自上向底进行的操作。
线段树操作中有push_up()和push_down()操作
1、懒人标记（lazy tag）的应用（后面具体会描述）
2、递归操作的运用
以下是具体操作：
首先
对于空间，我们需要开 ans[4*h],num[h],tag[4*h]，一般对于h个节点，开（h<<2）的空间。
其次
我们需要定义如下几个辅助函数：
1、左右孩子节点
inline int lch(int p){return p<<1;} inline int rch(int p){return p<<1|1;}
这里使用位运算不是为了装x
2、自下向上递归的操作
inline void push_up(int p){ans[p]=ans[lch(p)]+ans[rch(p)];} //ans[p]=max(ans[lch(p)],ans[rch(p)]) //ans[p]=func(ans[lch[p]],ans[[rch(p)]])
即当程序自子树向上递归的时候，完成线段树区间的更新
3、递归建树
void build(int p,int l,int r){ tag[p]=0;//懒人节点初始化，后面会讲 if(l==r){ans[p]=num[l];return;} //只有叶子节点才真正存储每一个单个元素 int mid=l+(r-l)/2; //递归建树 build(lch(p),l,mid); build(rch(p),mid+1,r); push_up(p); }
4、lazy tag and update（：
update函数含义是：给定p节点（代表[l,r]区间，给定需要修改的区间[L,R]，需要修改的操作k，对[l,r]这个区间进行这个操作）
思想：对于区间[L，R]进行的修改，如果大于[l,r]，那么[l,r]区间对于[l,mid],[mid+1,r]的修改可以暂时不做，毕竟爷懒，用个tag[p]存下这次的操作，留到下次再进行操作。
但是，在之后对于小于[l,r]区间的操作一定要清空之前的标记过没有做的工作，于是我们有了push_down（）操作，用于自p到叶子节点的更新，要放在递归前。
inline void f(int p,int l,int r,int k) { /* *这个函数代表对于代表[l,r]区间的p节点每个数字加上k */ ans[p]+=k*(r-l+1); tag[p]+=k;//这个容易忽略！这一层懒人节点清空掉不代表下一层也清掉 } inline void push_down(int p,int l,int r){ int mid=l+(r-l)/2; f(lch(p),l,mid,tag[p]); f(rch(p),mid+1,r,tag[p]); tag[p]=0;//清0 } void update(int L,int R,int l,int r,int k,int p){ if(L<=l&&r<=R){ ans[p]+=k*(r-l+1);//这里以对于区间每个数加k为例子 tag[p]+=k;//记录下未做的工作 return; } push_down(p,l,r);//清理之前没做的操作 int mid=l+(r-l)/2; if(R<=mid)update(L,R,l,mid,k,lch(p)); if(L>mid)update(L,R,mid+1,r,rch(p)); push_up(p);//当然要往回重新更新一遍啦 }
最后
查询操作
对于区间[q_l,q_r]的查询，不就是要查询[l,r]区间中包含[q_l,q_r]部分的查询嘛
int query(int q_x,int q_y,int l,int r,int p) { int res=0; if(q_x<=l&&r<=q_y)return ans[p]; int mid=(l+r)>>1; push_down(p,l,r);//清空可能出现的懒人操作 //递归查询 if(q_x<=mid)res+=query(q_x,q_y,l,mid,p*2); if(q_y>mid)res+=query(q_x,q_y,mid+1,r,p*2+1); return res; }
呼，总算写完啦。
不，最后贴上线段树模板的完整代码(与上述函数有些许不同，但是我懒的改了)
#include <iostream> #define ll long long using namespace std; const int maxn=1e6+1; unsigned ll n,m,a[maxn],ans[maxn<<2],tag[maxn<<2];//对于h个节点，一般开4h的空间 void scan(); inline void f(ll p,ll l,ll r,ll k) { tag[p]=tag[p]+k; ans[p]=ans[p]+k*(r-l+1); } inline void push_down(ll p,ll l,ll r) { ll mid=(l+r)>>1; f(p*2,l,mid,tag[p]); f(p*2+1,mid+1,r,tag[p]); tag[p]=0; } inline void push_up(ll p){ ans[p]=ans[2*p]+ans[2*p+1]; } void build(ll p,ll l,ll r){ tag[p]=0; if(l==r){ans[p]=a[l];return;} ll mid=l+((r-l)>>1); build(2*p,l,mid); build(2*p+1,mid+1,r); push_up(p); } void update(ll x,ll y,ll k,ll l,ll r,ll p){ if(x<=l&&y>=r){ ans[p]+=k*(r-l+1); tag[p]+=k; return; } ll mid=(l+r)/2; push_down(p,l,r); if(x<=mid)update(x,y,k,l,mid,p*2); if(y>mid)update(x,y,k,mid+1,r,p*2+1); push_up(p); } ll query(ll q_x,ll q_y,ll l,ll r,ll p) { ll res=0; if(q_x<=l&&r<=q_y)return ans[p]; ll mid=(l+r)>>1; push_down(p,l,r); if(q_x<=mid)res+=query(q_x,q_y,l,mid,p*2); if(q_y>mid)res+=query(q_x,q_y,mid+1,r,p*2+1); return res; } int main() { ll a1,b,c,d,e,f; scan(); build(1,1,n); while(m--){ scanf("%lld",&a1); switch(a1){ case 1: scanf("%lld%lld%lld",&b,&c,&d); update(b,c,d,1,n,1); break; case 2: scanf("%lld%lld",&e,&f); printf("%lld\n",query(e,f,1,n,1)); break; } } return 0; } void scan(){ cin>>n>>m; for(int i=1;i<=n;++i)scanf("%lld",&a[i]); }
原文：https://www.cnblogs.com/CicacdaTwelve/p/14626731.html
