# [模板] 权值线段树

$$A = [1, 2, 2, 2, 3, 3, 4]$$

## 权值线段树的作用

• 求某个数 $x$ 的排名
• 求排名为 $x$ 的数值
• 求某个数的前驱
• 求某个数的后继
• 插入某个数
• 删除某个数

## 插入与删除操作

inline void update(int root, int left, int right, int num, int v){
int lc = root << 1, rc = root << 1 | 1, mid = (left + right) >> 1;

if(left == right){
tree[root] += v;
return;
}

if(num <= mid)
update(lc, left, mid, num, v);
else
update(rc, mid+1, right, num, v);

tree[root] = tree[lc] + tree[rc];
}


## 查询第 $k$ 大元素

inline int queryK(int root, int left, int right, int num){
int lc = root << 1, rc = root << 1 | 1, mid = (left + right) >> 1;

if(left == right)
return left;

if(tree[lc] >= num)
return queryK(lc, left, mid, num);
else
return queryK(rc, mid+1, right, num - tree[lc]);
}


## 查询 $x$ 的排名

inline int query(int root, int left, int right, int qleft, int qright){
int lc = root << 1, rc = root << 1 | 1, mid = (left + right) >> 1;

if(qleft <= left && right <= qright){
return tree[root];
}

int ans = 0;

if(qleft <= mid)
ans += query(lc, left, mid, qleft, qright);
if(qright > mid)
ans += query(rc, mid+1, right, qleft, qright);

return ans;
}

inline int rank(int x){
if(x <= 1){
return 1;
}

return query(1, 1, SIZE, 1, x-1) + 1;
}


## 查询前驱

inline int find_pre(int root, int left, int right){
int lc = root << 1, rc = root << 1 | 1, mid = (left + right) >> 1;

if(left == right)
return left;

if(tree[rc])
return find_pre(rc, mid+1, right);

return find_pre(lc, left, mid);
}

inline int pre(int root, int left, int right, int num){
int lc = root << 1, rc = root << 1 | 1, mid = (left + right) >> 1;

if(right < num){
if(tree[root])
return find_pre(root, left, right);
return 0;
}

int ans = 0;

if(mid < num - 1 && tree[rc] && (ans = pre(rc, mid+1, right, num)))
return ans;

return pre(lc, left, mid, num);

}


## 查询后继

inline int find_next(int root, int left, int right){
int lc = root << 1, rc = root << 1 | 1, mid = (left + right) >> 1;

if(left == right)
return left;

if(tree[lc])
return find_next(lc, left, mid);

else find_next(rc, mid+1, right);
}

inline int next(int root, int left, int right, int num){
int lc = root << 1, rc = root << 1 | 1, mid = (left + right) >> 1;

if(num < left){
if(tree[root])
return find_next(root, left, right);
return 0;
}

int ans = 0;

if(num < mid && tree[lc] && (ans = next(lc, left, mid, num)))
return ans;

return next(rc, mid+1, right, num);
}