结构体实现

静态区间

• 区间每个元素加val，区间求和
• 区间修改$A$或$B$，求区间和$\sum A_i\times B_i$

动态开点

动态开点线段树更耗空间，不过不用离散化处理。

• 指针new对象实现
• 逻辑指针实现

非结构体实现

• 单点修改，区间覆盖，区间和，二分查找

线段树上二分

#define ls (id<<1)
#define rs (id<<1|1)
int hsz = heights.size();
vector<int> mx(4*(hsz+5), 0);
function<void(int,int,int)> build = [&](int id, int l, int r) {
    if (l==r) {
        mx[id] = heights[l];
        return ;
    }
    int m = l+r>>1;
    build(ls, l, m);
    build(rs, m+1, r);
    mx[id] = max(mx[ls], mx[rs]);
};
build(1, 0, hsz-1);
// 查询[ql, n)中大于v的最小下标，没有为-1
function<int(int,int,int,int,int)> ask_suf = [&](int id, int l, int r, int ql, int v) {
    if (mx[id] <= v) return -1; // 当前区间最大值不大于v，所以返回-1
    if (l == r) return l; // 到达最小区间直接返回索引
    int m = l+r>>1; 
    if (ql <= m) { // ql是落在左区间，左区间找不到则去右区间找
        int lrt = ask_suf(ls, l, m, ql, v);
        if (lrt != -1) return lrt;
        return ask_suf(rs, m+1, r, ql, v);
    } else { // 左区间不含大于等于ql的索引，只要遍历右区间
        return ask_suf(rs, m+1, r, ql, v);
    }
};
// 查询[0, qr]中大于v的最小下标，没有为-1
function<int(int,int,int,int,int)> ask_pre = [&](int id, int l, int r, int qr, int v) {
    if (mx[id] <= v) return -1; // 当前区间最大值不大于v，所以返回-1
    if (l == r) return l; // 到达最小区间直接返回索引
    int m = l+r>>1; 
    if (m < qr) { // qr是落在右区间，左区间找不到则去右区间找
        int lrt = ask_pre(ls, l, m, qr, v);
        if (lrt != -1) return lrt;
        return ask_pre(rs, m+1, r, qr, v);
    } else { // 右区间不含大于等于ql的索引，只要遍历左区间
        return ask_pre(rs, m+1, r, qr, v);
    }
};
// 查询[ql, qr]中大于v的最小下标，没有为-1
function<int(int,int,int,int,int,int)> ask = [&](int id, int l, int r, int ql, int qr, int v) {
    if (mx[id] <= v) return -1; // 当前区间最大值不大于v，所以返回-1
    if (l == r) return l; // 到达最小区间直接返回索引
    int m = l+r>>1; 
    if (m < ql) { // [ql, qr] 不含[l,m]区间，只含[m+1, r]区间
        return ask(rs, m+1, r, ql, qr, v);
    } else if (qr<m+1) { // [ql, qr] 只含[l,m]区间，不含[m+1, r]区间
        return ask(rs, l, m, ql, qr, v);
    } else { // 确保最小下标，先找左区间，再找右区间
        int lrt = ask(ls, l, m, ql, qr, v);
        if (lrt != -1) return lrt;
        return ask(rs, m+1, r, ql, qr, v);
    }
};