1、线段树是什么？

线段树（Segment Tree）是一种经典的数据结构，它是一颗二叉树，每个节点都代表区间。线段树用于解决静态区间问题和动态区间问题。

它的主要思想是将区间划分成若干个小区间，每个节点代表一个小区间。每个节点的值都是该区间内所有元素的某个函数（如和、最大值、最小值等）的值。在线段树中，每个节点有两个儿子，分别代表该节点所表示区间的左半部分和右半部分。这种表示方法可以在O(logN)的时间内完成区间操作，所以非常适合处理区间问题。

2、如何建立线段树？

对于一个给定的区间[left, right]，如果该区间不是叶节点，则将该区间划分为两个区间[mid + 1, right]和[left, mid]。若该区间为叶节点，则将该节点的值赋为该区间的元素值。

void build(int l,int r, int rt){//建立线段树，【l,r】 是当前区间 if(l==r){Sum[rt]=A[l];return;}int m=(l+r)>>1;build(l,m,rt<<1);build(m+1,r,rt<<1|1);pushup(rt);//更新节点信息 
}

2.1 如何查询区间操作？

考虑查询区间[begin, end]的和。首先将该区间[left, right]不断地分成两个子区间，直到区间[left, right]完全被包含于[begin, end]内。然后计算该区间内元素的和。

void PushDown(int rt,int ln,int rn){//ln,rn为左子树，右子树的数字数量。 if(Add[rt]){//下推标记 Add[rt<<1]+=Add[rt];Add[rt<<1|1]+=Add[rt];//修改子节点的Sum使之与对应的Add相对应 Sum[rt<<1]+=Add[rt]*ln;Sum[rt<<1|1]+=Add[rt]*rn;//清除本节点标记 Add[rt]=0;}
}int query(int L,int R,int l,int r,int rt){if(L<=l&&r<=R){return Sum[rt];}int m=(l+r)>>1;//下推标记，否则Sum可能不正确PushDown(rt,m-l+1,r-m); int ans=0;if(L<=m)//左子区间与[L,R]有重叠，递归 ans+=query(L,R,l,m,rt<<1);if(R>m)//右子区间与[L,R]有重叠，递归 ans+=query(L,R,m+1,r,rt<<1|1);return ans;
}

2.2 如何更新区间元素？

假设要将区间中第i个元素的值更新为v。首先找到线段树中对应节点，更新节点的值，并递归向上更新所有祖先节点的值。

void update(int num,int c,int l,int r,int rt){//【l,r】 是当前区间,点修改 if(l==r){Sum[rt]+=c;return;}int m=(l+r)>>1;if(num<=m)update(num,c,l,m,rt<<1);else update(num,c,m+1,r,rt<<1|1);pushup(rt);//更新了子节点之后，本节点也要更新 
}

接下来，我们通过一个简单的例子来更加深刻地理解线段树的思想。

3、例子

题目描述：给定一个长度为N的序列，支持两种操作：将区间[left, right]中的每个元素加上v，并查询区间[begin, end]的和。

Solution:

建立线段树

因为序列的长度为N，所以形成的线段树的叶节点个数应该为N。因此，在线段树的构造过程中，每个节点要么是叶节点，要么至少有一个儿子。所以，表示线段树的数组的长度应该是4*N。

void buildST(int p, int left, int right) { if (left == right) { //如果该区间为叶节点 ST[p] = A[left]; return; } int mid = (left + right) / 2; buildST(p * 2, left, mid); //建立左子树 buildST(p * 2 + 1, mid + 1, right); //建立右子树 ST[p] = ST[p * 2] + ST[p * 2 + 1]; //计算该节点的值 
}

由于ST[p]代表区间[left, right]的和，ST[p * 2]代表区间[left, mid]的和，ST[p * 2 + 1]代表区间[mid + 1, right]的和，因此，ST[p]的值可以直接从ST[p * 2]和ST[p * 2 + 1]的值计算得来，即ST[p] = ST[p * 2] + ST[p * 2 + 1]。

查询区间操作

void queryST(int p, int left, int right, int begin, int end) { if (begin <= left and end >= right) { //如果该区间[left, right]被包含于[begin, end]内         ans += ST[p]; //计算该区间的和 return; } int mid = (left + right) / 2; if (begin <= mid) { queryST(p * 2, left, mid, begin, end); //查询左子树 } if (end > mid) { queryST(p * 2 + 1, mid + 1, right, begin, end); //查询右子树 } 
}

更新区间元素

void updateST(int p, int left, int right, int index, int value) { if (left == right) { //找到线段树中对应节点 ST[p] += value; //更新该节点的值 return; } int mid = (left + right) / 2; if (index <= mid) { updateST(p * 2, left, mid, index, value); //更新左子树 } else { updateST(p * 2 + 1, mid + 1, right, index, value); //更新右子树 } ST[p] = ST[p * 2] + ST[p * 2 + 1]; //递归向上更新该节点的祖先节点的值 
}

至此，我们可以轻松地解决这个问题了。