$\%$ 板

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7;
int n, m, q, l, r, x;
int a[N], sum[4 * N];
void pushup(int rt)
{
	sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void build(int l, int r, int rt)//建树 
{
	if(l == r){ sum[rt] = 0; return;}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}
void update(int l, int r, int rt, int x, int d)//单点修改 
{
	if(l == r){ sum[rt] = d; return;}
	int mid = (l + r) >> 1;
	if(x <= mid) update(l, mid, rt << 1, x, d);
	else update(mid + 1, r, rt << 1 | 1, x, d);
	pushup(rt);
}
int query(int l, int r, int rt, int x, int y)//区间查询 
{
	if(x > r || y < l) return 0;
	if(x <= l && r <= y) return sum[rt];//区间[x,y]包含[l,r]
	int mid = (l + r) >> 1;
	int ans = 0;
	if(x <= mid) ans += query(l, mid, rt << 1, x, y);
	if(y > mid) ans += query(mid + 1, r, rt << 1 | 1, x, y);
	return ans;
}
int kth(int l, int r, int rt, int k)//求第k小的数 
{
	if(l == r) return r;//到达叶子结点
	int mid = (l + r) >> 1;
	int lsum = sum[rt << 1];
	if(k <= lsum) return kth(l, mid, rt << 1, k);
	return kth(mid + 1, r, rt << 1 | 1, k - lsum);
}
int pre(int x)//查找前驱 
{
	int k = query(1, N, 1, 1, x - 1);
	if(!k) return -1;//它是最小值，无前驱
	return kth(1, N, 1, k); 
} 
int next(int x, int mx)
{
	int k = query(1, N, 1, 1, x - 1) + 1;
	if(!(k ^ mx)) return -1;//它是最大值，无前驱
	return kth(1, N, 1, k); 
}
int main()
{

    return 0;
}

动态开点

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7;
struct node{
    int lson, rson, sum;
}T[N * 3];
int n, opt, x, cnt = 1, root = 1;
void update(int rt, int l, int r, int k, int v)//更新数值 
{
    if(l == r){
        T[rt].sum += v;
        return;
    }
    int mid = (l + r) >> 1;
    if(k <= mid){
    	if(!T[rt].lson) T[rt].lson = ++cnt;
    	update(T[rt].lson, l, mid, k, v);
	}
    else{
    	if(!T[rt].rson) T[rt].rson = ++cnt; 
    	update(T[rt].rson, mid + 1, r, k, v);
	}
    T[rt].sum = T[T[rt].lson].sum + T[T[rt].rson].sum;//类似pushup 
}
int query(int l, int r, int rt, int x, int y)//区间求和
{ 
    if(rt == 0)return 0;
    if(x <= l && r <= y) return T[rt].sum; 
    int s = 0;
    int mid = (l + r) >> 1;
    if(x <= mid) s += query(T[rt].lson, l, mid, x, y);
    if(y > mid) s += query(T[rt].rson, mid + 1, r, x, y);
    return s;
}
int kth(int rt, int l, int r, int k)//找第K个数 
{
    if(l == r) return r;
    int mid = (l + r) >> 1;
    int lson = T[rt].lson;
    int rson = T[rt].rson;
    if(T[lson].sum >= k)return kth(lson, l, mid, k);//左子树总数量>=k，那么第k个肯定在左子树 
    return kth(rson, mid + 1, r, k - T[lson].sum);//第k个在右子树，递归右子树，注意k值的变化
}
int main()
{
	
	return 0;
}