算法数据结构学习笔记

1.主席树

朴素做法，对于每一个版本都新建一个线段树，显然炸空间

我们考虑修改之后只有修改的点到根节点被修改，我们可以新建这些节点，并与未修改的节点连接

主席树模板：动态第k大

前置知识：权值线段树查找第k大

对于1~i建一个主席树，再通过其前缀性质相减，最后查询即可

1.离散化

STL大法好，sort，unique，lowerbound一套带走

2.如何储存主席树

const int maxn = 2e5+5;
struct node
{
	int l,r,sum;
}hjt[maxn*40];
int cnt,root[maxn];

由于我们需要存历史版本，所以不用初始建树

插入函数

void insert(int l,int r,int pre,int &p,int x)
{
	hjt[++cnt]=hjt[pre];
    p=cnt;
    hjt[now].sum++;
    if(l==r)
        return;
    int mid=(l+r)>>1;
    if(x<=mid)
        insert(l,mid,hjt[pre].l,hjt[p].l,x);
    else 
        insert(mid+1,r,hjt[pre].r,hjt[p].r,x);
}

询问第k大

int query(int l,int r,int lp,int rp,int k)
{
   	if(l==r)
        return l;
	int tmp = hjt[hjt[rp].l].sum-hjt[hjt[lp].l].sum;
    if(k<=tmp)
        return query(l,mid,hjt[lp].l,hjt[rp].l,k);
    else 
        return query(mid+1,r,hjt[lp].r,hjt[rp].r,k-tmp);
}

2.可持久化数组

模板题：LGP3919

奇技淫巧：STL rope

//rope
#include<ext/rope>

rope是个块状链表，支持O(1)复制

正解：主席树

1.用原数组建立一个普通线段树

2.根据题意建立版本

3.点分治

例题：POJ 1741

对于给定的一颗树，求两点距离不超过k的点对数量

首先简化问题，路径经过一个点的两点距离不超过k的点对数量

那么，就以该点作为根节点，预处理出所有点到根节点的距离，设为(dist[i])

然后对其进行排序，再双指针扫一遍求出符合要求的点对数目

但很显然，当两点的LCA不是所选的根节点时，不符合题意，我们需要容斥

对于根节点的每一个子树，我们再把其所有dist进行排序，再求出加和大于k的即可。

解决了这个之后，原问题就很好解决了，只需要把刚才那个根节点删除，并继续重复上述操作即可

为了使得这个操作次数尽量少，我们每次选取的节点应为树的重心

所以，整个算法的流程就是：

1.找树的重心

2.以该点为根结点，处理出所有dist

3.排序，双指针计算和大于k的

4.容斥，找子树中大于k的，计算答案

5.重复1