线段树原理及存储：
如图，1即为根节点，存储着[1,5]的整个区间和，‘1’为左边界，‘5’为右边界，所以此节点表示的是[1,5]这个区间。
线段树的每个节点向下二分，左儿子的编号为此节点 \(× 2\)，右儿子的编号为此节点 \(× 2 + 1\)，也就是数组存完全二叉树的做法。
所以，线段树可以直接用一个结构体来存：
struct Node{
int l, r;
ll sum; //和最好用long long来存，因为一般会爆int
}tr[4 * N]; //线段树节点个数最多为4倍n
线段树的单点修改，区间查询
线段树的建立
从根节点开始建树，更新当前节点左右边界信息后递归建立左右儿子。
如果当前节点为叶节点，即l == r时，那么它所代表的这个区间就只有一个值，就将此节点的sum更新为这一个值（即下面的a[l]）。
每层递归的最后，再把当前节点的sum更新为左儿子的sum加上右儿子的sum。
因此，我们一般会写一个pushdown函数，用来往上更新。
void pushup(int u){
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
这样，在build函数的最后，我们就可以直接用一个pushup函数来更新当前节点的sum了。
void build(int u, int l, int r){
tr[u]={l, r};
if(l == r){
tr[u].sum = a[l];
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
线段树的单点修改（很少用）
单点修改很简单，从根节点往下二分，逐步锁定要修改的节点，如果为叶节点，就直接修改即可。
然后最后还要用子节点的信息更新自己，保证值正确。
具体代码如下：
void update(int u, int x, int k){ //节点编号为u，要将第x个节点加上k
if(tr[u].l == tr[u].r){ //如果是叶节点，说明这就是要找的，直接加上就可以了
tr[u].sum += k;
return;
}
int mid = tr[u].l + tr[u].r >> 1;//还没找到就向下二分，找出mid
if(x <= mid) update(u << 1, x, k);//如果x在左半边，就向左半边递归
else update(u << 1 | 1, x, k); //否则向右递归
pushup(u); //更新当前节点信息
}
线段树一般不会这么用，因为如果只是单点修改，区间查询的话肯定就用树状数组，无论是在代码长度，编码和调试难度，乃至时间，空间上都是树状数组更优。
这里只是简单做一个讲解，方便理解后面的区间修改。
线段树的区间查询
查询时类似，也是从根节点开始递归。
但是这次要应对的是一个区间，所以略有不同。
具体代码如下：
ll query(int u, int l, int r){ //节点编号为u，要查询[l, r]这个区间
if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
//如果当前区间已经全部被包含在要查询的区间中，就直接返回sum即可
ll sum = 0; //记录和
int mid = tr[u].l + tr[u].r >> 1; //同理二分
if(l <= mid) sum += query(u << 1, l, r);
//如果要查询的区间与左半部分有交集，就要加上左半部分的和，继续递归左边
if(r > mid) sum += query(u << 1 | 1, l, r);
//如果与右边有交集就同理加上右边并递归。
//这里注意两个if一定要分开写，不能直接else，因为有可能要查找的区间卡在中间，左右两边都要加一遍
return sum; //最后一定要记得返回sum的值
}
最后的整合代码（可AC洛谷 P3374 【模板】树状数组 1）
线段树一般不会拿来单点修改，这里只是从简单说起，后面的区间修改要涉及到 \(\texttt{lazy_tag}\)(懒标记) 才是重点。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 500010;
int n, m;
int a[N];
struct Node{
int l, r;
ll sum;
}tr[4 * N];
void pushup(int u){
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r){
tr[u]={l, r};
if(l == r){
tr[u].sum = a[l];
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void update(int u, int x, int k){
if(tr[u].l == tr[u].r){
tr[u].sum += k;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) update(u << 1, x, k);
else update(u << 1 | 1, x, k);
pushup(u);
}
ll query(int u, int l, int r){
if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
ll sum = 0;
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) sum += query(u << 1, l, r);
if(r > mid) sum += query(u << 1 | 1, l, r);
return sum;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
build(1, 1, n);
int op, x, y;
for(int i = 1; i <= m; ++i){
scanf("%d%d%d", &op, &x, &y);
if(op == 1) update(1, x, y);
else printf("%lld\n", query(1, x, y));
}
return 0;
}
线段树的区间修改，区间查询
区间修改相对于单点修改，就要复杂一些了。
我们首先考虑如果向单点修改那样，对区间中的每个元素注意修改，那就要修改 \(n\) 次，每次修改有需要 \(logn\) 的时间，那总复杂度就到了 \(nlogn\) ，比暴力还差，那还玩啥啊？
于是，这种情况下，\(\texttt{lazy_tag}\) 它就应运而生了。
\(\texttt{lazy_tag}\) 的具体原理
\(\texttt{lazy_tag}\) 其实就是在每次修改到一个完全被包含的节点的时候，就直接更改这个节点上的区间和sum，然后再这个节点上打一个标记（懒标记，即\(\texttt{lazy_tag}\)）。在之后再查询到这个节点，而且需要继续往下分的时候，再把它的懒标记往下传递到它的左右两个子节点中，这样就避免了大量不必要的操作，大大降低了时间复杂度。
区间修改，区间查询的代码
首先，在线段树的每个节点中多存一个add，表示当前的\(\texttt{lazy_tag}\) ，即这个节点的每个子节点的区间中的每个元素还要加上add。
然后，我们还要专门写一个pushdown函数，来把懒标记下传。
void pushdown(int u){
Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
//为了方便，先定义一下根节点，左、右子节点
if(root.add){ //有标记才下传
left.sum += (left.r - left.l + 1) * root.add;
right.sum += (right.r - right.l + 1) * root.add;
//左右节点的sum和加上它们的区间长度乘上根节点的add
left.add += root.add;
right.add += root.add;
//左右节点的add也要加上根节点的add
root.add = 0;
//根节点的add记得清零
}
}
然后就是区间修改的函数
void update(int u, int l, int r, int k){
if(l <= tr[u].l && tr[u].r <= r){
tr[u].sum += (tr[u].r - tr[u].l + 1) * k;
tr[u].add += k;
//如果当前节点已被所求区间全部包含，直接把此节点的sum更新，并把add加上k，然后直接返回
return;
}
pushdown(u); //在二分之前先看看是否需要下传标记
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) update(u << 1, l, r, k);
if(r > mid) update(u << 1 | 1, l, r, k);
//后面和之前的单点修改同理，只是注意这里的l, r, k都是直接传下去的，因为后面的修改也是看整个所求区间
pushup(u); //最后记得要pushup一下
}
还有区间查询的函数，有一些改动
ll query(int u, int l, int r){
if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
pushdown(u); //其实就只是在需要分开算的时候pushdown一下就可以了(*^v^*)
ll sum = 0;
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) sum += query(u << 1, l, r);
if(r > mid) sum += query(u << 1 | 1, l, r);
return sum;
}
整合代码（可AC洛谷 P3372 【模板】线段树 1）
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100010;
int n, m;
int a[N];
struct Node{
int l, r;
ll add; //add最好也用long long
ll sum;
}tr[4 * N];
void pushup(int u){
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r){
tr[u]={l, r, 0}; //记得把add初始化为0
if(l == r){
tr[u].sum = a[l];
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void pushdown(int u){
Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if(root.add){
left.sum += (left.r - left.l + 1) * root.add;
right.sum += (right.r - right.l + 1) * root.add;
left.add += root.add;
right.add += root.add;
root.add = 0;
}
}
void update(int u, int l, int r, int k){
if(l <= tr[u].l && tr[u].r <= r){
tr[u].sum += (tr[u].r - tr[u].l + 1) * k;
tr[u].add += k;
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) update(u << 1, l, r, k);
if(r > mid) update(u << 1 | 1, l, r, k);
pushup(u);
}
ll query(int u, int l, int r){
if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
ll sum = 0;
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) sum += query(u << 1, l, r);
if(r > mid) sum += query(u << 1 | 1, l, r);
return sum;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
build(1, 1, n);
int op, x, y, k;
while(m--){
scanf("%d%d%d", &op, &x, &y);
if(op == 1){
scanf("%d", &k);
update(1, x, y, k);
}
else{
printf("%lld\n", query(1, x, y));
}
}
return 0;
}