正文
线段树（build，insert，dfs操作）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
模板原型：
解决零散数点在已知线段上的出现次数。思想是将线段用长线覆盖，将长线转化成线段树。用权值记录各个数点出现的次数，最后进行查询。代码解释见注释。
#include <bits/stdc++.h>
using namespace std; const int MAXN = 3e4 + ;
int n, m, l, r; //长度n，线段数m struct line {
int left, right; //left:左边界 right:右边界
int n; //该节点的权值
} a[MAXN]; void buildt(int l, int r, int step){
a[step].left = l; //建立当前节点的左边界赋值
a[step].right = r; //建立当前节点的右边界赋值
a[step].n = ; //初始化当前节点的权值
if(l == r) {return; } //如果是叶子节点，不进行下面的递归建树操作
buildt(l, (l + r) / , step * ); //递归建立左结点
buildt((l + r) / + , r, step * + ); //递归建立右结点
} void dfs(int step){
cout << step << " " //当前节点下标
<< a[step].left << " " //结点左边界
<< a[step].right << " " //结点右边界
<< a[step].n << endl; //结点对应权值
if(a[step].left == a[step].right) return;//若为叶子结点，结束当前节点深搜
dfs(step * ); //递归搜索左结点
dfs(step * + ); //递归搜索右结点
return ;
} void insert(int s, int t, int step){
if(s == a[step].left && t == a[step].right) {
++ a[step].n; //插入的线段匹配则该条线段的记录 +1
return ; //插入操作成功，返回
} if(a[step].left == a[step].right) //如果当前线段没有子节点，返回
return ; int mid = (a[step].left + a[step].right) / ; //二分思想确立中值mid if(mid >= t) { //如果中值在t的右边
insert(s, t, step * ); //则插入到左儿子 } else if (mid < s) { //如果中值在s的左边
insert(s, t, step * + );//则插入到右儿子 } else {
insert(s, mid, step * );//否则中点将线段划分，左端到中点部分放入左结点
insert(mid + , t, step * + );//中点到右端部分放入右结点
}
return ;
} int main(){
cout << MAXN << endl;
cin >> n >> m;
buildt(, n, );
//dfs(1);
for(int i = ; i < m; i ++ ) {
cin >> l >> r;
insert(l, r, );
}
dfs();
return ;
}
