树链剖分 --不一样的详解

欢迎转载,转载请注明来自 bestsort的博客 并保留该超链接

算了算自己大大小小也看了不下十几篇关于树链剖分的博客了吧,但是总感觉差强人意,基本上都是一上来就告诉读者我们来先背几个概念,然后就是 轻儿子重儿子重边重链 什么的一股脑全堆上来.但是个人感觉这种方式对初学者并不友好! 笔者不才,打算自己根据对树链剖分的理解重新写一篇真正适合入门的详解

---

这里,笔者打算以 What-How-Why(黄金圈法则) 的方式进行讲解.先知道树链剖分是什么,它有什么用,再去了解它怎么实现,具体原理是什么

What

树链剖分是什么

树链剖分就是将树分割成多条链，然后利用数据结构（线段树、树状数组等）来维护这些链。

实际上,这些链是一条条平躺着放在数组里面的

How

映射的规则

上文中说过树链剖分是把树分割成多条链,并将其映射到一维数组

当然分割是要讲道理滴!自然要遵循某些规则

这里的规则很简单,那就是

在一维区间中,对于任意树上结点 x, 则 x 的所有子孙结点都在以 x 为起点的一段连续区间内(当然,树链还有一些其他的约束条件,我们放到后面再说)

很难理解?

比如说 我有下图这颗树

)

我们可以构造出下面这些区间,都满足上面的规则.(注意是任意结点 x 都满足规则)

#分别对应 [ABDCEF],[BD],[CEF]
ABDCEF

#[ACEFBD],[CEF],[BD]
ACEFBD

#[ACFEBD],[CFE],[BD]
ACFEBD

也就是说映射到最后的结果是:对于任意节点 x, x 和它的子树在区间内一定连续的

---

对于这个规则,我们不难想到,其实就是一个 DFS 的事情(想不通的可以看一下二叉树的前中后序遍历出来的结果).

Ok, 现在我们知道了,要用 DFS 将树映射成一维区间.可是遍历顺序有没有影响?

有的!

而正是因为分割规则的不同,才有长链剖分和重链剖分这两种说法,本文只讲重链剖分.当然不是说长链剖分就没用,两者在不同的场合都有各自的优势,这里不赘述了

回到上文,遍历顺序是对最终的复杂度有影响的.这里举一个具体的例子,如下图:

---

有点懒,不想写了….具体的待补充

---

题目链接 先放代码占坑,过几天有空再写

    
#include <bits/stdc++.h>

using namespace std;
#define mem(a, b) memset(a, b, sizeof a)
#define IN freopen("in.txt", "r", stdin)
#define DEBUG(a) cout << (a) << endl

typedef long long ll;
int dir8[8][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int dir4[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
const int INF = 0x3f3f3f3f;
int mod = 1e9 + 7;
const int maxn = 1e6 + 10;

struct edge
{
    int next, to;
    /* data */
} e[maxn];
int cnt;
int head[maxn];
void addEdge(int u, int v)
{
    e[++cnt] = {head[u], v};
    head[u] = cnt;
}
struct node
{
    int l, r, flag, w;
    int dis() { return r - l + 1; }
    int mid() { return (r + l) / 2; }
    /* data */
} a[maxn];

int rt;
int cn;
int w[maxn];
int bufW[maxn];
int id[maxn],fa[maxn],top[maxn], son[maxn], dep[maxn], sz[maxn];

void dfs1(int u, int f, int deep)
{
    dep[u] = deep;
    sz[u] = 1;
    fa[u] = f;

    int maxSon = -1;
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == f)
            continue;
        dfs1(v, u, deep + 1);
        sz[u] += sz[v];
        if (sz[v] > maxSon)
        {
            son[u] = v;
            maxSon = sz[v];
        }
    }
}

void dfs2(int u, int ttop)
{
    id[u] = ++cn;
    w[cn] = bufW[u];
    top[u] = ttop;
    if (!son[u])
        return;
    dfs2(son[u], ttop);
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (v == fa[u] || v == son[u])
            continue;
        dfs2(v, v);
    }
}

void build(int k, int l, int r)
{
    a[k] = {l, r, 0, 0};
    if (a[k].l == a[k].r)
    {
        a[k].w = w[r];
        return;
    }
    build(k << 1, l, (r + l) / 2);
    build(k << 1 | 1, (r + l) / 2 + 1, r);
    a[k].w = a[k << 1].w + a[k << 1 | 1].w;
    a[k].w %= mod;
}

void down(int k)
{
    a[k << 1].w += a[k << 1].dis() * a[k].flag;
    a[k << 1 | 1].w += a[k << 1 | 1].dis() * a[k].flag;
    a[k << 1].flag += a[k].flag;
    a[k << 1 | 1].flag += a[k].flag;
    a[k].flag = 0;
}
void update(int k, int l, int r, int val)
{
    if (a[k].l >= l && a[k].r <= r)
    {
        a[k].w += val * a[k].dis();
        a[k].flag += val;
        return;
    }
    if (a[k].flag)
        down(k);
    if (a[k].mid() >= l)
        update(k << 1, l, r, val);
    if (a[k].mid() < r)
        update(k << 1|1, l, r, val);
    a[k].w = a[k << 1].w + a[k << 1 | 1].w;
    a[k].w %= mod;
}

int query(int k, int l, int r)
{
    if (a[k].l >= l && a[k].r <= r)
        return a[k].w;
    int res = 0;
    if (a[k].flag)
        down(k);
    if (a[k].mid() >= l)
        res += query(k << 1, l, r);
    if (a[k].mid() < r)
        res += query(k << 1 | 1, l, r);
    return res % mod;
}

void updateRange(int p1,int p2,int val){
    while (top[p1] != top[p2])
    {
        if(dep[top[p1]] < dep[top[p2]])
            swap(p1,p2);
        update(1,id[top[p1]],id[p1],val);    
        p1 = fa[top[p1]];
    }
    if(dep[p1] > dep[p2])
        swap(p1,p2);
    update(1,id[p1],id[p2],val);
}

int queryRange(int p1,int p2){
    int ans = 0;
    while (top[p1]!=top[p2])
    {
        if(dep[top[p1]] < dep[top[p2]])
            swap(p1,p2);
        ans += query(1,id[top[p1]],id[p1]);
        ans %= mod;
        p1 = fa[top[p1]];
    }
    if(dep[p1] > dep[p2])
        swap(p1,p2);
    return (ans + query(1,id[p1],id[p2]))%mod;
}

void updateSon(int p,int val){
    update(1,id[p],id[p]+sz[p]-1,val);
}
int querySon(int p){
    return query(1,id[p],id[p]+sz[p]-1)%mod; 
}

int main()
{
    //IN;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,k,m,rt;
    cin >> n >> m >> rt >> mod;
    for(int i=1;i<=n;i++)
        cin >> bufW[i];
    int u,v;

    for(int i=1;i<n;i++){
        cin >> u >> v;
        addEdge(u,v);
        addEdge(v,u);
    }

    dfs1(rt,0,1);
    dfs2(rt,rt);
    build(1,1,n);

    int l, r, w;
    while (m--)
    {
        //  debug(n);
        cin >> k;
        if (k == 1)
        {
            cin >> l >> r >> w;
            updateRange(l, r, w);
        }
        else if (k == 2)
        {
            cin >> l >> r;
            DEBUG(queryRange(l, r));
        }
        else if (k == 3)
        {
            cin >> l >> w;
            updateSon(l, w);
        }
        else
        {
            cin >> l;
            DEBUG(querySon(l));
        }
    }

    return 0;
}