线段树相关问题 (引用 PKU POJ题目) 整理
1.RangeMinimum、Maximum Query问题（计算单调区间内出现最多（少）的次数）
对元素的起点做离散化，再把离散化后的位置作为线段树的[l, r),记录次数为t.
对输入区间a, b:
如果（a = b）{很好处理}，
如果（a = b – 1）{分别计算a、b的次数，取大（小）的一项}，
如果（a < b – 1）{分别计算a、b的次数和线段树[a + 1, b – 1)的次数，取大（小）的一项};
pku3264-Balanced Lineup RMQ问题,求区间最大最小值的差
pku3368-Frequent values 转化为RMQ问题求解
2.排队插队问题(ID为i的人插到第j位，求最后序列)
先把插队顺序记录下来，然后倒序插入。用线段树记录已有的序列，计算当前人物的序号,注意重复插入的情况(重复插入则结果序列中只处理第一次出现位置)。 线段树记录[i, j)中的已插入的人数，所以每次插入都是insert(n, n + 1)，Query函数和一般的find有所不同,传入的是偏移量，通过偏移量计算. 忘了哪道题了，反正有的。
3.矩形交求面积/周长
对纵坐标离散化并做扫描线。
如果求周长则记录原始y轴覆盖段数ocn，原始和当前覆盖区域长度ocl，cl，则ans+=abs(ocl-cl)+ocn*(x_now-x_pre)
如果计算面积只需要记录原始覆盖区域长度ocl，然后ans+=ocl*(x_now-x_pre)
pku1151-Atlantis 求矩形并的面积,用线段树+离散化+扫描线
pku1177-picture 求矩形并的周长,用线段树+离散化+扫描线
4.覆盖涂色查找颜色种数问题
把坐标离散化，注意边界如果是整数，右边+1取开区间，防止出现[(1,10),(1,3),(6,10)]输出为2的情况。
离散化可以放在线段树里，尽量不要用map离散化（效率问题），Insert到字节点时，先把父节点颜色插入子节点并重置父节点为未涂色。
查询时查询涂色子节点数量即可
pku2528-Mayor's posters 区间涂色问题,使用离散化+线段树
注意开线段树的大小，由于用数组模拟有空间浪费，注意不要RE，一般节点数可设为最大子节点数的8倍
注意离散化尽量用sort取不重复点而不是用map，用sort的效率大约是map的10倍
相关代码：
普通线段树[无离散化]：
struct _SegTree_Data
{
int l, r;
int v;
};
struct SegTree
{
const static int maxn = 500000;
_SegTree_Data data[4 * maxn];
//初始化函数（如果需要）
void init(int l, int r, int f = 0)
{
data[f].l = l;
data[f].r = r;
data[f].v = 0;
if(r > l + 1)
{
int m = (l + r) / 2;
init(l, m, 2 * f + 1);
init(m, r, 2 * f + 2);
}
}
//参数：插入区间[l,r),区间父结点[f]
void insert(int l, int r, int f = 0)
{
//根据需要修改
data[f].v ++;
if(data[f].l == l && data[f].r == r)
return;
//--------------
int m = (data[f].l + data[f].r) / 2;
if(l >= m)//区间在右子节点上
insert(l, r, 2 * f + 2);
else if(r <= m)//区间在作左子节点上
insert(l, r, 2 * f + 1);
else
insert(l, m, 2 * f + 1), insert(m, r, 2 * f + 2);
}
//参数：查找区间[l,r),区间父结点[f]
//返回：区间值
int find(int l, int r, int f = 0)
{
if(data[f].l == l && data[f].r == r)
return data[f].v;
int m = (data[f].l + data[f].r) / 2;
if(l >= m)//区间在右子节点上
return find(l, r, 2 * f + 2);
else if(r <= m)//区间在作左子节点上
return find(l, r, 2 * f + 1);
else // 根据需要修改
return find(l, m, 2 * f + 1) + find(m, r, 2 * f + 2);
}
//排队问题的查找位置函数
//参数：插入位置[rp](相对父结点起始位置的偏移),区间父结点[f]
//返回：实际位置
int query(int rp, int f = 0)
{
if(data[f].v == 0)
return data[f].l + rp;
int lc = 2 * f + 1;
int ll = data[lc].r - data[lc].l - data[lc].v;//计算左子节点剩余位置数量
//注意rp是偏移量[0,rp],ll是个数[1,ll]
if(rp < ll)//目标在左子节点中
return query(rp , lc);
else//目标在右子节点中
return query(rp - ll, lc + 1);
}
};矩形交[MAP离散化]：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
//注释代码为计算周长时使用
struct SegTree;
//用于离散化y轴坐标
std::map<double, int> hash;//离散化映射
std::map<double, int>::iterator itr;
double mapOf[2 * 10500];//离散化位置对应的值
struct _SegTree
{
int l, r;//作用域[l,r)
int c/*, cn*/;//全覆盖次数[c]，覆盖区间段数[cn]
double cl;//覆盖区域长度[cl]
//bool lc, rc;//左顶点覆盖[lc]，右顶点覆盖[rc]
_SegTree(){}
_SegTree(int l, int r)
{
this->l = l;
this->r = r;
//lc = rc = false;
c /*= cn*/ = 0;
cl = 0.0;
}
};
struct SegTree
{
const static int maxn = 10500;
_SegTree data[4 * maxn];
//初始化，置零
void init(int l, int r, int f = 0)
{
data[f] = _SegTree(l, r);
if(r - l > 1)
{
int m = (l + r) / 2;
init(l, m, 2 * f + 1);
init(m, r, 2 * f + 2);
}
}
//插入区间[l,f)
void insert(int l, int r, int f = 0)
{
if(data[f].l == l && data[f].r == r)
data[f].c ++;
else
{
int m = (data[f].l + data[f].r) / 2;
int lc = 2 * f + 1;
if(l >= m)//区间在右子节点
insert(l, r, lc + 1);
else if(r <= m)//区间在左子节点
insert(l, r, lc);
else
insert(l, m, lc), insert(m, r, lc + 1);
}
update(f);
}
//删除区间
void del(int l, int r, int f = 0)
{
if(data[f].l == l && data[f].r == r)
data[f].c --;
else
{
int m = (data[f].l + data[f].r) / 2;
int lc = 2 * f + 1;
if(l >= m)//区间在右子节点
del(l, r, lc + 1);
else if(r <= m)//区间在左子节点
del(l, r, lc);
else
del(l, m, lc), del(m, r, lc + 1);
}
update(f);
}
//更新记录状态集
void update(int f = 0)
{
if(data[f].c > 0)//全覆盖判断
{
//data[f].lc = data[f].rc = true;
data[f].cl = mapOf[data[f].r] - mapOf[data[f].l];//离散化的还原
//data[f].cn = 1;
return;
}
else if(data[f].r - data[f].l <= 1)//单位节点
{
//data[f].lc = data[f].rc = false;
data[f].cl = 0.0;
//data[f].cn = 0;
return;
}
int lc = 2 * f + 1;
data[f].cl = data[lc].cl + data[lc + 1].cl;
//data[f].cn = data[lc].cn + data[lc + 1].cn;
//if(data[lc].rc == true && data[lc + 1].lc == true)
//data[f].cn --;
//data[f].lc = data[lc].lc;
//data[f].rc = data[lc + 1].rc;
}
};
struct node
{
double x, uy, dy;
bool isAdd;
node(){}
node(double x, double uy, double dy, bool isAdd): x(x), uy(uy), dy(dy), isAdd(isAdd){}
};
SegTree root;//线段树
node ls[2 * SegTree::maxn];//输入矩阵
bool cmp(node l, node r)
{
if(l.x != r.x)
return l.x < r.x;
if(l.isAdd != r.isAdd)
return l.isAdd;
return l.dy < r.dy;
}
int main()
{
int n, hl;
while(::scanf("%d", &n), n)
{
double ans = 0;
double lux, luy, rlx, rly;
root.init(0, SegTree::maxn);
hash.clear();
for(int i = 0; i < n; i ++)
{
//读入左上角和右下角
::scanf("%lf %lf %lf %lf", &lux, &luy, &rlx, &rly);
ls[2 * i] = node(lux, rly, luy, true);
ls[2 * i + 1] = node(rlx, rly, luy, false);
hash[rly] = hash[luy] = 0;
}
for(hl = 0, itr = hash.begin(); itr != hash.end(); itr ++, hl ++ )
itr->second = hl, mapOf[hl] = itr->first;
std::sort(ls, ls + 2 * n, cmp);//排序后从左到右扫描
double preX = ls[0].x;
for(int i = 0; i < 2 * n; i ++)
{
double ocl = root.data[0].cl;
//int ocn = root.data[0].cn;
if(ls[i].isAdd)
root.insert(hash[ls[i].dy], hash[ls[i].uy]);
else
root.del(hash[ls[i].dy], hash[ls[i].uy]);
//求周长
//ans += (ls[i].x - preX) * 2 * ocn;
//ans += abs(ocl - root.data[0].cl);
//求面积
ans += ocl * (ls[i].x - preX);
if(ls[i].x > preX)
preX = ls[i].x;
}
::printf("%.2lf\n", ans);
}
return 0;
}涂色覆盖问题[[Sort数值离散化]：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
int map[20010];// 用于离散化
int seg[10005][2];
bool check[10005];
struct _SegTree_Data
{
int l, r;
int v;//区间覆盖颜色，夹缝覆盖颜色
bool leaf;//叶节点
};
struct SegTree
{
const static int maxn = 10005;
_SegTree_Data data[8 * maxn];
//初始化函数（如果需要）
void init(int l, int r, int f = 0)
{
data[f].l = map[l];
data[f].r = map[r];
data[f].v = 0;
if(r > l + 1)
{
int m = (l + r) / 2;
init(l, m, 2 * f + 1);
init(m, r, 2 * f + 2);
data[f].leaf = false;
}
else
data[f].leaf = true;
}
//参数：插入区间[l,r),插入值[v],区间父结点[f]
void insert(int l, int r, int v, int f = 0)
{
//根据需要修改
if(data[f].l == l && data[f].r == r)
{
data[f].v = v;
return;
}
//--------------
int m = data[2 * f + 2].l;
if(data[f].v > 0)
{
data[2 * f + 1].v = data[2 * f + 2].v = data[f].v;
data[f].v = 0;
}
if(l >= m)//区间在右子节点上
insert(l, r, v, 2 * f + 2);
else if(r <= m)//区间在作左子节点上
insert(l, r, v, 2 * f + 1);
else
insert(l, m, v, 2 * f + 1), insert(m, r, v, 2 * f + 2);
}
//参数：查找区间父结点[f]
//返回：段数
int find(int f = 0)
{
if(data[f].v > 0)
{
if(!check[data[f].v])
{
check[data[f].v] = true;
return 1;
}
return 0;
}
if(data[f].leaf == false)
return find(2 * f + 1) + find(2 * f + 2);
return 0;
}
};
SegTree root;
int main()
{
int t;
scanf("%d", &t);
while(t --)
{
int n, rn;
scanf("%d", &n);
for(int i = 0; i < n; i ++)
{
scanf("%d %d", &seg[i][0], &seg[i][1]);
map[2 * i] = seg[i][0];
map[2 * i + 1] = seg[i][1] + 1;//注意右边界为开区间
}
memset(check, false, sizeof(check));
std::sort(map, map + 2 * n);
rn = 1;
for(int i = 1; i < 2 * n; i ++)//去除重复点
if(map[i] != map[i - 1])
map[rn ++] = map[i];
root.init(0, rn - 1);
check[0] = true;
for(int i = 0; i < n; i ++)
root.insert(seg[i][0], seg[i][1] + 1, i + 1);
printf("%d\n", root.find());
}
return 0;
}二维线段树（这段不是自己写的Copy来的）：
//下面我就简单介绍一下我理解中的二维线段树。顾名思义，二维线段树需要有两个维度，所以实现它的最基本思想就是树中套树。假设有一个矩形横坐标范围1—n，纵坐标范围1—m。我们可以以横坐标为一个维度，建立一棵线段树，假设为tree1，在这棵树的每个节点中以纵坐标建立一棵线段树，设为tree2，假设我们在tree1所处在的节点的的横坐标范围为l,r，那么该节点表示的矩形范围为横坐标为l—r，纵坐标范围为1—m。若我们正处在该节点中tree2的某个节点，该节点的纵坐标范围为d—u，那么tree2中的这个节点所代表的矩形范围，横坐标l—r，纵坐标d—u。所以千万不要糊涂应该怎么树中套树，仔细想想其实思想就是这么简单，我们要知道二维线段树并不是一棵树，我们不能把其统一成某种能表示平面的节点，而是根据各个节点的含义组合出能表示平面的节点。
//代码
//1：定义数据结构：
//
// 一维线段树的节点定义。
typedef struct
{
int l, r; // 线段左右端点坐标
int mv; // 该线段范围内的最大值
} NodeOne;
//一维线段树的类定义。
struct OneDemonTree
{
const int maxn = 1005;
NodeOne data[3 * maxn]; // 节点数组
void init(int l, int r, int step); // 建立线l—r线段树
void insert(int l, int r, int var, int step); // 把var插入到线段l—r中
void delet(int l, int r, int step); // 删除l—r线段
int query(int l, int r, int step); // 查询l---r的最大值
};
//二维线段树节点定义：
typedef struct
{
int l, r; // 横坐标范围l—r，
OneDemonTree tree; // 以纵坐标建立的线段树
} NodeTwo;
//二维线段树类定义：
struct TwoDemonTree
{
const int maxn = 1005;
int l, r; // 横坐标范围l—r，
NodeTwo data[3 * maxn]; //二维线段树节点数组
// 建立横坐标范围为xl-xr，纵坐标范围yd—yu的线段树。
void init(int xl, int xr, int yd, int yu, int step);
// 在xl-xr yd-yu 的矩形范围内插入var
void insert(int xl, int xr, int yd, int yu, int var, int step);
// 删除…
void delet(int xl, int xr, int yd, int yu, int step);
//查询xl-xr yd-yu 范围内的最大值
int query(int xl, int xr, int yd, int yu, int step);
};
//2： 操作实现：
//一维线段树初始化、插入、查询操作
void OneDemonTree::init(int l, int r, int step)
{
data[step].l = l;
data[step].r = r;
data[step].mv = 0;
if(l == r)
return;
int mid = (l + r) >> 1;
init(l, mid, 2 * step);
init(mid + 1, r, 2 * step + 1);
}
void OneDemonTree::insert(int l, int r, int var, int step)
{
if(data[step].mv < var)
data[step].mv = var;
if(data[step].l == data[step].r)
return;
int mid = (data[step].l + data[step].r) >> 1;
if(l <= mid)
insert(l, r, var, 2 * step);
if(r > mid)
insert(l, r, var, 2 * step + 1);
int v = data[2 * step].mv > data[2 * step + 1].mv ? data[2 * step].mv : data[2 * step + 1].mv;
if(data[step].mv < v)
data[step].mv = v;
}
int OneDemonTree::query(int l, int r, int step)
{
if(l <= data[step].l && r >= data[step].r)
return data[step].mv;
int mid = (data[step].l + data[step].r) >> 1;
int mv = 0;
if(l <= mid)
mv = query(l, r, 2 * step);
if(r > mid)
{
int rs = query(l, r, 2 * step + 1);
if(rs > mv)
mv = rs;
}
return mv;
}
//二维线段树的建立、插入、查询操作：
void TwoDemonTree::init(int xl, int xr, int yd, int yu, int step)
{
data[step].l = xl;
data[step].r = xr;
data[step].tree.init(yd, yu, 1);
if(xl == xr)
return;
int mid = (xl + xr) >> 1;
init(xl, mid, yd, yu, 2 * step);
init(mid + 1, xr, yd, yu, 2 * step + 1);
}
void TwoDemonTree::insert(int xl, int xr, int yd, int yu, int var, int step)
{
data[step].tree.insert(yd, yu, var, 1);
if(data[step].l == data[step].r)
return;
int mid = (data[step].l + data[step].r) >> 1;
if(xl <= mid)
insert(xl, xr, yd, yu, var, 2 * step);
if(xr > mid)
insert(xl, xr, yd, yu, var, 2 * step + 1);
}
int TwoDemonTree::query(int xl, int xr, int yd, int yu, int step)
{
if(xl <= data[step].l && xr >= data[step].r)
return data[step].tree.query(yd, yu, 1);
int mid = (data[step].l + data[step].r) >> 1;
int rs = 0;
if(xl <= mid)
rs = query(xl, xr, yd, yu, 2 * step);
if(xr > mid)
{
int tmp = query(xl, xr, yd, yu, 2 * step + 1);
if(tmp > rs)
rs = tmp;
}
return rs;
}
//3：二维线段树的时空复杂度分析
//空间复杂度分析：
//一棵坐标范围为1-n的线段数的节点总数不超过3*N，那么二维线段树共需要3*N*3*M个节点，所以空间消耗为O(9*M*N)。
//时间复杂度分析：
//初始化：O(m*n*logm*logn)
//插入： O(logm*logn)。
//删除： O(logm*logn)。
//查询： O(logm*logn)。Last updated