树链剖分简单分析及模板(杂谈)

这几天学习了一下树链剖分,顺便写一下我的理解、

早上看了一下别人的讲解,云里雾里,终于算是搞懂了、

树链剖分是解决在树上进行插点问线,插线问点等一系列树上的问题

假如现在给你一棵树,然后没两条边之间有一条权值,有一些操作,1:x---y之间的最大权值是多少,2:改变x---y之间的权值

当前这样的操作有很多,如果直接用暴力的方法的话肯定不行,那么就要想一个好的方法,我们可以想一下能不能借助线段树解决,能不能想一种方法对树上的边进行编号,然后就变成区间了。那么我们就可以在线段树上进行操作了,树链剖分就是这样的一个算法

当然编号不是简单的随便编号,如果我们进行随便的编号,然后建立一个线段树,如果要更新一个边的权值,是log2(n)的复杂度,而查找的话,我们要枚举x--y的之间的所有的边,假如我们随便以一个点为根节点进行编号,最大的长度是树的直径,这个值本身是比较大的,而在线段树上查找任意一个区间的复杂度也是log2(n),这样查找一次的时间复杂度比直接暴力还要高,所以很明显是不行的。

那么就要想想办法了,我们能不能把x--y之间的一些边一块儿查找,这就是关于树链剖分的重边和轻边,

重边:某个节点x到孩子节点形成的子树中节点数最多的点child之间的边,由定义发现除了叶子节点其他节点只有一条重边

重边是可以放在一块儿更新的,而有

性质:从根到某一点的路径上轻边、重边的个数都不大于logn。

所以这样查找的时间复杂度相当于log2(n)

其实树链剖分就是把边哈希到线段树上的数据结构

实现的话很简单,用两个dfs处理数数的信息,重边以及轻边,然后就是一些线段树的操作了。

模板“:以spoj 375 为例

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <vector>
  4 #include <algorithm>
  5 using namespace std;
  6 #define Del(a,b) memset(a,b,sizeof(a))
  7 const int N = 10005;
  8 
  9 int dep[N],siz[N],fa[N],id[N],son[N],val[N],top[N]; //top 最近的重链父节点
 10 int num;
 11 vector<int> v[N];
 12 struct tree
 13 {
 14     int x,y,val;
 15     void read(){
 16         scanf("%d%d%d",&x,&y,&val);
 17     }
 18 };
 19 tree e[N];
 20 void dfs1(int u, int f, int d) {
 21     dep[u] = d;
 22     siz[u] = 1;
 23     son[u] = 0;
 24     fa[u] = f;
 25     for (int i = 0; i < v[u].size(); i++) {
 26         int ff = v[u][i];
 27         if (ff == f) continue;
 28         dfs1(ff, u, d + 1);
 29         siz[u] += siz[ff];
 30         if (siz[son[u]] < siz[ff])
 31             son[u] = ff;
 32     }
 33 }
 34 void dfs2(int u, int tp) {
 35     top[u] = tp;
 36     id[u] = ++num;
 37     if (son[u]) dfs2(son[u], tp);
 38     for (int i = 0; i < v[u].size(); i++) {
 39         int ff = v[u][i];
 40         if (ff == fa[u] || ff == son[u]) continue;
 41         dfs2(ff, ff);
 42     }
 43 }
 44 #define lson(x) ((x<<1))
 45 #define rson(x) ((x<<1)+1)
 46 struct Tree
 47 {
 48     int l,r,val;
 49 };
 50 Tree tree[4*N];
 51 void pushup(int x) {
 52     tree[x].val = max(tree[lson(x)].val, tree[rson(x)].val);
 53 }
 54 
 55 void build(int l,int r,int v)
 56 {
 57     tree[v].l=l;
 58     tree[v].r=r;
 59     if(l==r)
 60     {
 61         tree[v].val = val[l];
 62         return ;
 63     }
 64     int mid=(l+r)>>1;
 65     build(l,mid,v*2);
 66     build(mid+1,r,v*2+1);
 67     pushup(v);
 68 }
 69 void update(int o,int v,int val)  //log(n)
 70 {
 71     if(tree[o].l==tree[o].r)
 72     {
 73         tree[o].val = val;
 74         return ;
 75     }
 76     int mid = (tree[o].l+tree[o].r)/2;
 77     if(v<=mid)
 78         update(o*2,v,val);
 79     else
 80         update(o*2+1,v,val);
 81     pushup(o);
 82 }
 83 int query(int x,int l, int r)
 84 {
 85     if (tree[x].l >= l && tree[x].r <= r) {
 86         return tree[x].val;
 87     }
 88     int mid = (tree[x].l + tree[x].r) / 2;
 89     int ans = 0;
 90     if (l <= mid) ans = max(ans, query(lson(x),l,r));
 91     if (r > mid) ans = max(ans, query(rson(x),l,r));
 92     return ans;
 93 }
 94 
 95 int Yougth(int u, int v) {
 96     int tp1 = top[u], tp2 = top[v];
 97     int ans = 0;
 98     while (tp1 != tp2) {
 99         //printf("YES\n");
100         if (dep[tp1] < dep[tp2]) {
101             swap(tp1, tp2);
102             swap(u, v);
103         }
104         ans = max(query(1,id[tp1], id[u]), ans);
105         u = fa[tp1];
106         tp1 = top[u];
107     }
108     if (u == v) return ans;
109     if (dep[u] > dep[v]) swap(u, v);
110     ans = max(query(1,id[son[u]], id[v]), ans);
111     return ans;
112 }
113 void Clear(int n)
114 {
115     for(int i=1;i<=n;i++)
116         v[i].clear();
117 }
118 int main()
119 {
120     //freopen("Input.txt","r",stdin);
121     int T;
122     scanf("%d",&T);
123     while(T--)
124     {
125         int n;
126         scanf("%d",&n);
127         for(int i=1;i<n;i++)
128         {
129             e[i].read();
130             v[e[i].x].push_back(e[i].y);
131             v[e[i].y].push_back(e[i].x);
132         }
133         num = 0;
134         dfs1(1,0,1);
135         dfs2(1,1);
136         for (int i = 1; i < n; i++) {
137             if (dep[e[i].x] < dep[e[i].y]) swap(e[i].x, e[i].y);
138             val[id[e[i].x]] = e[i].val;
139         }
140         build(1,num,1);
141         char s[200];
142         while(~scanf("%s",&s) && s[0]!='D')
143         {
144             int x,y;
145             scanf("%d%d",&x,&y);
146             if(s[0]=='Q')
147                 printf("%d\n",Yougth(x,y));
148             if (s[0] == 'C')
149                 update(1,id[e[x].x],y);
150         }
151         Clear(n);
152     }
153     return 0;
154 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开发与安全

算法:队列与广度优先搜索(迷宫问题)

队列也是一组元素的集合,也提供两种基本操作:Enqueue(入队)将元素添加到队尾,Dequeue(出队)从队头取出元素并返回。就像排队买票一样,先来先服务,先...

3497
来自专栏Java爬坑系列

【Java入门提高篇】Day22 Java容器类详解(五)HashMap源码分析(上)

准备了很长时间,终于理清了思路,鼓起勇气,开始介绍本篇的主角——HashMap。说实话,这家伙能说的内容太多了,要是像前面ArrayList那样翻译一下源码,稍...

2455
来自专栏章鱼的慢慢技术路

排序算法的实现与比较

1758
来自专栏尾尾部落

[剑指offer] 二维数组中的查找

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个...

1152
来自专栏有趣的Python

python分布式爬虫搜索引擎实战-2-深度优先和广度优先

深度优先和广度优先 目录: 网站的树结构 深度优先算法和实现 广度优先算法和实现 网站url树结构: 分层设计 子域名: bogbole.com - blo...

44611
来自专栏图形学与OpenGL

实验4 类初步

 注:本次实验有可能会安排在校内http://acm.hpu.edu.cn/contest.php进行。

872
来自专栏来自地球男人的部落格

[LeetCode] 120. Triangle

【原题】 Given a triangle, find the minimum path sum from top to bottom. Each step...

1987
来自专栏Python小屋

Python计算信息熵

信息熵可以用来判定指定信源发出的信息的不确定性,信息越是杂乱无章毫无规律,信息熵就越大。如果某信源总是发出完全一样的信息,那么熵为0,也就是说信息是完全可以确定...

4784
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高十八】Map接口集合详解

四、Map接口 Map与List、Set接口不同,它是由一系列键值对组成的集合,提供了key到Value的映射。同时它也没有继承Collecti...

3666
来自专栏数据科学学习手札

(数据科学学习手札07)R在数据框操作上方法的总结(初级篇)

上篇我们了解了Python中pandas内封装的关于数据框的常用操作方法,而作为专为数据科学而生的一门语言,R在数据框的操作上则更为丰富精彩,本篇就R处理数据框...

3548

扫码关注云+社区

领取腾讯云代金券