线段树

线段树可以在 O( logN ) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

注意点：

• 线段树的数组一般要开到4 * N；  位运算的写法为 N >> 2
• 对于懒标记：修改的时候不用用到下面的区间，查询的时候才会用到下面的区间
  • 故每次插入懒标记不用递归到叶子节点

建树

void build(int u, int l, int r) {
    if (l == r) {  // 递归边界
        f[u] = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);  // 建左儿子
    build(u << 1 | 1, mid + 1, r);
    f[u] = f[u << 1] +
           f[u << 1 | 1];  // 父节点区间和 = 左儿子区间和 + 右儿子区间和
}

单点修改

// 当前修改 u 节点， u 节点所对应区间为[l, r] 要给 a[p] 加上 c
void add(int u, int l, int r, int p, int c) {
    f[u] += c;
    if (l == r)
        return;
    int mid = l + r >> 1;
    if (p <= mid)  // p 在左儿子区间
        add(u << 1, l, mid, p, c);
    else
        add(u << 1 | 1, mid + 1, r, p, c);
}

区间查询

// 当前为 u 节点， u 节点所对应区间为[l, r] 要查询[s, t]区间和
ll query(int u, int l, int r, int s, int t) {
    if (l == s && r == t)
        return f[u];
    int mid = l + r >> 1;
    if (t <= mid)  // 查询区间完全在左侧
        return query(u << 1, l, mid, s, t);
    else if (s > mid)  // 查询区间完全在右侧
        return query(u << 1 | 1, mid + 1, r, s, t);
    else  // 左侧部分 + 右侧部分     *注意修改查询区间的边界
        return query(u << 1, l, mid, s, mid) +
               query(u << 1 | 1, mid + 1, r, mid + 1, t);
}