线段树是一种很实用的数据结构，所以也要学习一下。 线段树是用来处理区间问题的，复杂度能到达 。 就以洛谷的模板题 线段树 1 为例吧。
1.将某区间每一个数加上x 2.求出某区间每一个数的和
很显然，这道题是要写一个维护区间和的线段树。 就拿代码说吧。
建树
因为线段树是一棵二叉树，所以如果一个结点的编号为 那么其左右子结点编号分别为 和 （用位运算可以如下表示）
cpp
#define ls (o << 1)
#define rs (o << 1 | 1)因为要维护区间和，所以要这么写。
cpp
void push_up(long long o) {
sum[o].v = sum[ls].v + sum[rs].v;
}递归建树。
如果左右区间相同说明它是叶子节点，所以就记录输入数据的信息然后 return 就好啦。
cpp
void build(long long o, long long l, long long r) {
sum[o].add = 0;
if (l == r) {
sum[o].v = a[l];
return;
}
build(ls, l, mid);
build(rs, mid + 1, r);
push_up(o);
}区间修改
我们用 add 记录每个节点每次要更新的值，传递式记录，这样有利于减少复杂度。
注意：add 在建树时就已经初始化好了，其实在这里也可以初始化。
下面用 delta() 函数来进行区间更新操作，因为是对区间进行操作，所以最后要乘上区间长度（即区间元素个数）。
push_down() 来维护区间更新，每次更新两个子节点并向下传递。
cpp
void delta(long long o, long long l, long long r, long long k) {
sum[o].add = sum[o].add + k;
sum[o].v = sum[o].v + k * (r - l + 1);
}
void push_down(long long o, long long l, long long r) {
delta(ls, l, mid, sum[o].add);
delta(rs, mid + 1, r, sum[o].add);
}下面的代码中，用 sb, se 表示要修改的区间，l, r 表示节点 o 所存的区间。(emm，参数有些长啊~~，但强迫症不想用 typedef~~)
cpp
void update(long long o, long long sb, long long se, long long l, long long r, long long k) {
if (sb <= l && se >= r) { // 如果到了区间端点就这么做
sum[o].v += k * (r - l + 1);
sum[o].add += k;
return;
} // 是不是很熟悉？这就是 delta() 的操作
push_down(o, l, r);
if (sb <= mid) update(ls, sb, se, l, mid, k);
if (se > mid) update(rs, sb, se, mid + 1, r, k);
push_up(o); // 回溯
}区间查询
依然是递归，如果在范围内就返回节点存的值，如果出了范围就返回 0。
cpp
long long query(long long o, long long sb, long long se, long long l, long long r) {
if (sb <= l && se >= r) return sum[o].v;
if (sb > r || se < l) return 0;
push_down(o, l, r);
return query(ls, sb, se, l, mid) + query(rs, sb, se, mid + 1, r);
}最终代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 3;
struct data {
long long v, add;
} sum[maxN << 2];
long long n, m;
long long a[maxN];
struct Tree {
#define ls (o << 1)
#define rs (o << 1 | 1)
#define mid ((r + l) >> 1)
void push_up(long long o) {
sum[o].v = sum[ls].v + sum[rs].v;
}
void build(long long o, long long l, long long r) {
sum[o].add = 0;
if (l == r) {
sum[o].v = a[l];
return;
}
build(ls, l, mid);
build(rs, mid + 1, r);
push_up(o);
}
void delta(long long o, long long l, long long r, long long k) {
sum[o].add = sum[o].add + k;
sum[o].v = sum[o].v + k * (r - l + 1);
}
void push_down(long long o, long long l, long long r) {
delta(ls, l, mid, sum[o].add);
delta(rs, mid + 1, r, sum[o].add);
}
void update(long long o, long long sb, long long se, long long l, long long r, long long k) {
if (sb <= l && se >= r) {
sum[o].v += k * (r - l + 1);
sum[o].add += k;
return;
}
push_down(o, l, r);
if (sb <= mid) update(ls, sb, se, l, mid, k);
if (se > mid) update(rs, sb, se, mid + 1, r, k);
push_up(o);
}
long long query(long long o, long long sb, long long se, long long l, long long r) {
if (sb <= l && se >= r) return sum[o].v;
if (sb > r || se < l) return 0;
push_down(o, l, r);
return query(ls, sb, se, l, mid) + query(rs, sb, se, mid + 1, r);
}
} tree;
int main() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++) scanf("%lld", a + i);
tree.build(1, 1, n);
while (m--) {
int c;
long long x, y, k;
scanf("%d%lld%lld", &c, &x, &y);
if (c == 1) {
scanf("%lld", &k);
tree.update(1, x, y, 1, n, k);
} else if (c == 2)
printf("%lld\n", tree.query(1, x, y, 1, n));
}
}