这是一棵一棵一棵线段树
众所周知，线段树是一个优质的维护区间信息（需要满足结合律）的数据结构
我们可以
-
\(O(nlogn)\) 建树
-
\(O(logn)\) 查询任意区间的信息
关于结合律：
\[\LARGE(a+b)+c=a+(b+c)
\]
so,如何建线段树呢？
首先，我们可以利用结构体封装来解决维护信息较多时的情况
struct Segtr
{
int l,r;// 线段树此节点维护的区间
ll sum; // 这个区间的和
int add; // 懒惰标记
// lc，rc为左儿子与右儿子，它们所维护的区间分别为[l, mid], [mid + 1, r]
#define lc (p << 1)
#define rc (p << 1 | 1)
} tr[N << 2]; // 开4倍空间防止RE
然后就是建树
inline void build(int p, int l, int r)
{
tr[p].l = l, tr[p].r = r, tr[p].add = 0;
if (l == r)
{
tr[p].sum = a[l]; // a存的是原数据
return; // 到达叶子节点返回
}
int mid = l + r >> 1; // 从中间分开
build(lc, l, mid); // 建左子树
build(rc, mid + 1, r); // 建右子树
pushup(p);
}
\(pushup()\) 函数是合并子区间的函数，具体见下
inline void pushup(int p)
{
tr[p].sum = tr[lc].sum + tr[rc].sum;
/* 显而易见，pushup不止可以这样写，在维护区间最大值时
tr[p].maxn = max(tr[lc].maxn, tr[rc].maxn);
所以这个函数根据维护值的不同而不同*/
}
接下来，就可以进行区间查询了
inline void query(int p, int ql, int qr) // ql与qr为查询区间，l与r为维护区间
{
int l = tr[p].l, r = tr[p].r;
// 这个节点的维护区间被询问区间完全覆盖，那么它所维护的值就一定会对答案产生贡献
if (ql <= l && qr >= r) return tr[p].sum;
pushdown(p); // 下传懒惰标记
int mid = l + r >> 1, ret = 0;
// query的初始p = 1，也就是说初始维护的区间为[1,n]
// 对其进行二分，查找符合条件的区间并入ret
if (ql <= mid) ret += query(lc, ql, qr), ret %= MOD; // 查左树
if (r > mid) ret += query(rc, ql, qr), ret %= MOD; // 查右树
return ret;
}
\(pushdown()\) 用于下传懒标，当然只有区间带修时才有用
inline void pushdown(int p)
{
int l = tr[p].l, r = tr[p].r, mid = l + r >> 1;
tr[lc].sum += (mid - l + 1) * tr[p].add;
tr[rc].sum += (r - l) * tr[p].add; // 用标记乘上区间长度为此区间的修改量
tr[lc].add += tr[p].add;
tr[rc].add += tr[p].add; // 下传懒标
tr[p].add = 0;
}
这样就可以愉快的写区修了
单修其实就是让 ql=qr
inline void modify(int p, int ql, int qr, int k)
{
int l = tr[p].l, r = tr[p].r;
if (ql <= l && qr >= r) // 完全覆盖
{
tr[p].sum += k * (r - l + 1);
tr[p].add += k;
}
pushdown(p);
int mid = l + r >> 1;
if (ql <= mid) modify(lc, ql, qr, k); // 递归修改左子树
if (qr > mid) modify(rc, ql, qr, k); // 递归修改右子树
pushup(p);
}
于是乎，我们便得到了一棵线段树