「树链剖分」点权 边权模板

学习树链剖分我看过以下博客：
树链剖分原理和实现
树链剖分整理总结

知道大概之后，我以为要多加深记忆的地方：
对于每一个重儿子，其top必然是其父亲的top，并且由于要用其它数据结构（如树状数组，线段树）等来维护，所以一条链在物理上存储是连续的。
那么如何连续起来？其实靠的是dfs1打的标记，一条重链的dfs序号必然连续。

了解这个之后，求u到v之间的某些数值，就可以更好地理解那些辅助的数据结构是如何操纵值的了。比如在树状数组中区间是[a,b]，那么要把[a，b]的值增加k，相当于add(a,k)，add(b+1,-k)。
参考kuangbin的模板，假设是基于点权，查询单点值，修改路径上的点权（HDU 3966 树链剖分+树状数组）

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
#define fi first
#define se second
#define pb push_back
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 5e4 + 5;

struct Edge {
    int to, next;
} edge[maxN * 2];

int head[maxN], tot;
int top[maxN];  // top[v]即v所在重链的顶端结点
int fa[maxN];   // 父节点
int deep[maxN]; // 深度
int num[maxN];  // num[v] 以v为根的子树结点数
int p[maxN];    // p[v]为v的dfs位置
int fp[maxN];   // 与p相反
int son[maxN];  // 重子编号
int pos;

void init() {
    tot = 0;
    // 使用bit 编号从1开始
    pos = 1;
    mst(head, -1);
    mst(son, -1);
}

void addEdge(int u, int v) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void dfs1(int u, int pre, int d) {
    deep[u] = d;
    fa[u] = pre;
    num[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v != pre) {
            dfs1(v, u, d + 1);
            num[u] += num[v];
            if (son[u] == -1 || num[v] > num[son[u]])
                son[u] = v;
        }
    }
}

void getPos(int u, int sp) {
    top[u] = sp;
    p[u] = pos++;
    fp[p[u]] = u;
    if (son[u] == -1)
        return;
    getPos(son[u], sp);
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v != son[u] && v != fa[u])
            getPos(v, v);
    }
}

int bit[maxN];
int n;
int sum(int i) {
    int s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}
int add(int i, int x) {
    while (i <= n) {
        bit[i] += x;
        i += i & -i;
    }
}

void modify(int u, int v, int val) {
    int f1 = top[u], f2 = top[v];
    int tmp = 0;
    while (f1 != f2) {
        if (deep[f1] < deep[f2]) {
            swap(f1, f2);
            swap(u, v);
        }
        add(p[f1], val);
        add(p[u] + 1, -val);
        u = fa[f1];
        f1 = top[u];
    }
    if (deep[u] > deep[v])
        swap(u, v);
    add(p[u], val);
    add(p[v] + 1, -val);
}

int a[maxN];
int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif

    int M, P;
    while (~scanf("%d%d%d", &n, &M, &P)) {
        int u, v;
        int C1, C2, K;
        char op[10];
        init();
        rep(i, 1, n + 1)
            scanf("%d", &a[i]);

        while (M--) {
            scanf("%d%d", &u, &v);
            addEdge(u, v);
            addEdge(v, u);
        }

        dfs1(1, 0, 0);
        getPos(1, 1);
        mst(bit, 0);

        rep(i, 1, n + 1) {
            add(p[i], a[i]);
            add(p[i] + 1, -a[i]);
        }

        while (P--) {
            scanf("%s", op);
            if (op[0] == 'Q') {
                scanf("%d", &u);
                printf("%d\n", sum(p[u]));
            } else {
                scanf("%d%d%d", &C1, &C2, &K);
                if (op[0] == 'D')
                    K = -K;
                modify(C1, C2, K);
            }
        }
    }
    return 0;
}

基于边权，修改单条边权，查询路径边权最大值（SPOJ QTREE 树链剖分+线段树）
那么，如何解决边权的计算问题呢？我们可以把边看作点。留意到树中节点可以有多条出边，但入边最多只有一条。故而我们可以拿点的序号来唯一表示边。
先根据点的关系完成树链剖分的工作。接着我们根据边在树链剖分时的序号（即dfs序号）操纵线段树即可。我想表达的是，线段树中的区间序号只与dfs1序号有关，它是不需明白点和边的意义的，这里不必想得复杂。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
#define fi first
#define se second
#define sz size()
#define lb lower_bound
#define ub upper_bound
#define pb push_back
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 1e4 + 5;
int N, M, T;

// 线段树 
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
int seg[maxN << 2];
void push_up(int rt) { seg[rt] = max(seg[rt << 1], seg[rt << 1 | 1]); }
void build(int l, int r, int rt) {
    seg[rt] = 0;
    if (l == r) return;
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
}
int query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R)
        return seg[rt];
    int m = (l + r) >> 1;
    int ret = 0;
    if (L <= m) ret = max(ret, query(L, R, lson));
    if (R > m) ret = max(ret, query(L, R, rson));
    return ret;
}
void update(int p, int x, int l, int r, int rt) {
    if (l == r) {
        seg[rt] = x;
        return;
    }
    int m = (r + l) >> 1;
    if (p <= m) update(p, x, lson);
    else update(p, x, rson);
    push_up(rt);
}

// 树链剖分
struct Edge {
    int to, next;
} edge[maxN * 2];

int head[maxN], tot;
int top[maxN];  // top[v]即v所在重链的顶端结点
int fa[maxN];   // 父节点
int deep[maxN]; // 深度
int num[maxN];  // num[v] 以v为根的子树结点数
int p[maxN];    // p[v]为v的dfs位置
int fp[maxN];   // 与p相反
int son[maxN];  // 重子编号
int pos;

void init() {
    tot = 0;
    pos = 0;
    mst(head, -1);
    mst(son, -1);
}

void addEdge(int u, int v) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void dfs1(int u, int pre, int d) {
    deep[u] = d;
    fa[u] = pre;
    num[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v != pre) {
            dfs1(v, u, d + 1);
            num[u] += num[v];
            if (son[u] == -1 || num[v] > num[son[u]])
                son[u] = v;
        }
    }
}

void getPos(int u, int sp) {
    top[u] = sp;
    p[u] = pos++;
    fp[p[u]] = u;
    if (son[u] == -1)
        return;
    getPos(son[u], sp);
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v != son[u] && v != fa[u])
            getPos(v, v);
    }
}

// 查询u->v边的max
int findMax(int u, int v) {
    int f1 = top[u], f2 = top[v];
    int tmp = 0;
    while (f1 != f2) {
        if (deep[f1] < deep[f2]) {
            swap(f1, f2);
            swap(u, v);
        }
        tmp = max(tmp, query(p[f1], p[u], 0, pos - 1, 1));
        u = fa[f1];
        f1 = top[u];
    }
    if (u == v) return tmp;
    if (deep[u] > deep[v]) swap(u, v);
    return max(tmp, query(p[son[u]], p[v], 0, pos - 1, 1));
}

int e[maxN][3];

// CHANGE i ti 修改第i条边的值为ti
// QUERY a b 询问a到b的最大边权
// DONE 结束符号
int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif

    scanf("%d", &T);
    while (T--) {
        init();
        scanf("%d", &N);
        rep(i, 0, N - 1) {
            scanf("%d%d%d", &e[i][0], &e[i][1], &e[i][2]);
            addEdge(e[i][0], e[i][1]);
            addEdge(e[i][1], e[i][0]);
        }
        dfs1(1, 0, 0);
        getPos(1, 1);
        build(0, pos - 1, 1);

        rep(i, 0, N - 1) {
            if (deep[e[i][0]] > deep[e[i][1]])
                swap(e[i][0], e[i][1]);
            update(p[e[i][1]], e[i][2], 0, pos - 1, 1);
        }
        char op[10];
        int u, v;
        while (~scanf("%s", op)) {
            if (op[0] == 'D') break;
            scanf("%d %d", &u, &v);
            if (op[0] == 'C')
                update(p[e[u - 1][1]], v, 0, pos - 1, 1);
            else
                printf("%d\n", findMax(u, v));
        }
    }
    return 0;
}

bzoj 1036 修改点权，问u，v路径上的点权之和，点权最大值

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
#define fi first
#define se second
#define sz size()
#define lb lower_bound
#define ub upper_bound
#define pb push_back
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 3e4 + 5;
int N, M, T;


// 线段树
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
int big[maxN << 2], sum[maxN << 2];
void push_up(int rt) {
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    big[rt] = max(big[rt << 1], big[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
    big[rt] = -inf;
    sum[rt] = 0;
    if (l == r)
        return;
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    push_up(rt);
}
void update(int p, int to, int l, int r, int rt) {
    if (l == r) {
        sum[rt] = to;
        big[rt] = to;
        return;
    }
    int m = (l + r) >> 1;
    if (p <= m) update(p, to, lson);
    else if (p > m) update(p, to, rson);
    push_up(rt);
}
// mode 1求和 2求最大值
int query(int L, int R, int l, int r, int rt, int mode) {
    if (L <= l && r <= R) {
        if (mode == 1) return sum[rt];
        else return big[rt];
    }
    int m = (l + r) >> 1;
    if (mode == 1) {
        int ret = 0;
        if (L <= m) ret += query(L, R, lson, 1);
        if (R > m) ret += query(L, R, rson, 1);
        return ret;
    } else {
        int ret = -inf * 2;
        if (L <= m) ret = max(ret, query(L, R, lson, 2));
        if (R > m) ret = max(ret, query(L, R, rson, 2));
        return ret;
    }
}

// 点权 树链剖分
struct Edge { int to, next; } edge[maxN * 2];
int head[maxN], tot;
int top[maxN];
int fa[maxN];
int deep[maxN];
int num[maxN];
int p[maxN];
int fp[maxN];
int son[maxN];
int pos;

void init() { tot = 0; pos = 1; mst(head, -1); mst(son, -1); }
void addEdge(int u, int v) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
void dfs1(int u, int pre, int d) {
    deep[u] = d;
    fa[u] = pre;
    num[u] = 1;
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v == pre) continue;
        dfs1(v, u, d + 1);
        num[u] += num[v];
        if (son[u] == -1 || num[v] > num[son[u]])
            son[u] = v;
    }
}
void getPos(int u, int sp) {
    top[u] = sp;
    p[u] = pos++;
    fp[p[u]] = u;
    if (son[u] == -1) return;
    getPos(son[u], sp);
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (v != son[u] && v != fa[u])
            getPos(v, v);
    }
}

int getMax(int u, int v) {
    int f1 = top[u], f2 = top[v];
    int tmp = -inf;
    while (f1 != f2) {
        if (deep[f1] < deep[f2]) {
            swap(f1, f2);
            swap(u, v);
        }
        tmp = max(tmp, query(p[f1], p[u], 1, N, 1, 2));
        u = fa[f1], f1 = top[u];
    }
    if (deep[u] > deep[v]) swap(u, v);
    return max(tmp, query(p[u], p[v], 1, N, 1, 2));
}
int getSum(int u, int v) {
    int f1 = top[u], f2 = top[v];
    int s = 0;
    while (f1 != f2) {
        if (deep[f1] < deep[f2]) {
            swap(f1, f2);
            swap(u, v);
        }
        s += query(p[f1], p[u], 1, N, 1, 1);
        u = fa[f1], f1 = top[u];
    }
    if (deep[u] > deep[v]) swap(u, v);
    return s += query(p[u], p[v], 1, N, 1, 1);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif

    scanf("%d", &N);
    init();
    int u, v;
    rep(i, 0, N - 1) {
        scanf("%d%d", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
    }
    dfs1(1, 0, 0);
    getPos(1, 1);
    build(1, N, 1);
    int w;
    rep(i, 1, N + 1) {
        scanf("%d", &w);
        update(p[i], w, 1, N, 1);
    }
    scanf("%d", &T);
    char op[10];
    while (T--) {
        scanf("%s %d %d", op, &u, &v);
        if (op[1] == 'M')
            printf("%d\n", getMax(u, v));
        else if (op[1] == 'S')
            printf("%d\n", getSum(u, v));
        else
            update(p[u], v, 1, N, 1);
    }
    return 0;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 205,132评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 87,802评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,566评论 0赞 338
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,858评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,867评论 5赞 368
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,695评论 1赞 282
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,064评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,705评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 42,915评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,677评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,796评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,432评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,041评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,992评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,223评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,185评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,535评论 2赞 343