树链剖分小结

入门的话，这篇还是写的不错的：http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html

个人认为，其实树链剖分并不是一个复杂的算法或者数据结构，只是能把一棵树拆成链来处理而已，换一种说法，树链剖分只是xxx数据结构/算法在树上的推广，或者说，树链剖分只是把树hash到了几段连续的区间上。

因为这东西本身没有功能，具体功能都是靠具体数据结构实现的，所以复杂度就是O(logn * ??)。如果套上了线段树，就是 O(log^2 n)。如果套上了树套树，那就是O(log^3 n)。如果你用树链剖分和树套树写区间第k大，那就是O(log^4 n)。

另外，树链剖分具体实现的时候是给边重新编号还是给点重新编号，这得根据不同的题目而定，实现的时候要注意顶端那个编号能不能取。

对了，这东西可以顺便求LCA。比如说基于点的剖分，就是剖分到两个点都到同一条重链的时候，比较上端的那个点。

下面是一些例题：

SPOJ375 QTREE 基于边的重编号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

#include <cstdio>
#include <cstring>
#include <algorithm>

const int MAXN = 10001;
int LinkSize;
struct Edge
{
  int v, w;
  Edge *next;
} g[MAXN*2], *header[MAXN];
int s[MAXN*4];
void add_edge(const int x, const int y, const int w)
{
  Edge *node = g+(LinkSize++);
  node->v = y;
  node->w = w;
  node->next = header[x];
  header[x] = node;
}
typedef int Matrix[MAXN+1];
int TestData, n, road[MAXN][3];
int _st, _ed, _x;
void _modify(const int p, const int lef, const int rig)
{
  if (lef == rig)
  {
    s[p] = _x;
    return;
  }
  const int mid = (lef+rig)/2;
  if (_st <= mid) _modify(p*2, lef, mid);
  if (mid+1 <= _ed) _modify(p*2+1, mid+1, rig);
  s[p] = std::max(s[p*2], s[p*2+1]);
}
int _query(const int p, const int lef, const int rig)
{
  if (_st <= lef && rig <= _ed)
    return s[p];
  const int mid = (lef+rig)/2;
  int res = 0;
  if (_st <= mid) res = std::max(res, _query(p*2, lef, mid));
  if (mid+1 <= _ed) res = std::max(res, _query(p*2+1, mid+1, rig));
  return res;
}
inline void Modify(const int pos, const int x)
{
  _st = _ed = pos, _x = x;
  _modify(1, 1, n);
}
inline int Query(const int lef, const int rig)
{
  _st = lef, _ed = rig;
  return _query(1, 1, n);
}
Matrix depth, size, top, parent, hson, number;
void dfs(const int u)
{
  size[u] = 1, hson[u] = 0;
  for (Edge *e = header[u]; e; e = e->next)
    if (e->v != parent[u])
    {
      parent[e->v] = u;
      depth[e->v] = depth[u]+1;
      dfs(e->v);
      size[u] += size[e->v];
      if (size[e->v] > size[hson[u]])
        hson[u] = e->v;
    }
}
int TreeSize;
void build_tree(const int u, const int tp)
{
  number[u] = ++TreeSize, top[u] = tp;
  if (hson[u])
    build_tree(hson[u], tp);
  for (Edge *e = header[u]; e; e = e->next)
    if (e->v != parent[u] && e->v != hson[u])
      build_tree(e->v, e->v);
}

inline int GetMax(int a, int b)
{
  int ta = top[a], tb = top[b], res = 0;
  while (ta != tb)
  {
    if (depth[ta] < depth[tb])
      std::swap(ta, tb), std::swap(a, b);
    res = std::max(res, Query(number[ta], number[a]));
    a = parent[ta], ta = top[a];
  }
  if (a == b) return res;
  if (depth[a] > depth[b]) std::swap(a, b);
  return std::max(res, Query(number[hson[a]], number[b]));
}
void Solve()
{
  scanf("\n%d", &n);
  LinkSize = TreeSize = 0;
  memset(s, 0, sizeof(*s)*4*n);
  memset(header+1, 0, sizeof(*header)*n);

  for (int i = 1; i < n; ++i)
  {
    scanf("%d%d%d", &road[i][0], &road[i][1], &road[i][2]);
    add_edge(road[i][0], road[i][1], road[i][2]);
    add_edge(road[i][1], road[i][0], road[i][2]);
  }
  dfs(1);
  build_tree(1, 1);
  for (int i = 1; i < n; ++i)
  {
    if (depth[road[i][0]] > depth[road[i][1]])
      std::swap(road[i][0], road[i][1]);
    Modify(number[road[i][1]], road[i][2]);
  }
  for (int x, y; ; )
  {
    static char s[10];
    scanf("\n%s", s);
    if (s[0] == 'D') return;
    scanf("%d%d", &x, &y);
    if (s[0] == 'Q')
      printf("%d\n", GetMax(x, y));
    else
      Modify(number[road[x][1]], y);
  }
}
int main()
{
  scanf("%d", &TestData);
  while (TestData--)
  {
    Solve();
  }
}

bzoj1036 基于点的重编号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

#include <cstdio>
#include <algorithm>

const int MAXN = 30001;
struct Edge { int v; Edge *next; };
struct Node { int value, max, sum; };
Edge g[MAXN*2], *header[MAXN];
Node s[MAXN*2];
int n, m;
void AddEdge(const int x, const int y)
{
  static int LinkSize;
  Edge* const node = g+(LinkSize++);
  node->v = y;
  node->next = header[x];
  header[x] = node;
}

int _st, _ed, _x;
int _query_max(const int p, const int lef, const int rig)
{
  if (_st <= lef && rig <= _ed) return s[p].max;
  const int mid = (lef+rig)/2;
  int res = static_cast<int>(0x80000000UL);
  if (_st <= mid) res = _query_max(p*2, lef, mid);
  if (mid+1 <= _ed) res = std::max(res, _query_max(p*2+1, mid+1, rig));
  return res;
}
int _query_sum(const int p, const int lef, const int rig)
{
  if (_st <= lef && rig <= _ed) return s[p].sum;
  const int mid = (lef+rig)/2;
  int res = 0;
  if (_st <= mid) res += _query_sum(p*2, lef, mid);
  if (mid+1 <= _ed) res += _query_sum(p*2+1, mid+1, rig);
  return res;
}
void _modify(const int p, const int lef, const int rig)
{
  if (lef == rig)
  {
    s[p].value = s[p].max = s[p].sum = _x;
    return;
  }
  const int mid = (lef+rig)/2;
  if (_st <= mid) _modify(p*2, lef, mid);
  if (mid+1 <= _ed) _modify(p*2+1, mid+1, rig);
  s[p].max = std::max(s[p*2].max, s[p*2+1].max);
  s[p].sum = s[p*2].sum + s[p*2+1].sum;
}
inline int QueryMax(const int lef, const int rig)
{
  _st = lef, _ed = rig;
  return _query_max(1, 1, n);
}
inline int QuerySum(const int lef, const int rig)
{
  _st = lef, _ed = rig;
  return _query_sum(1, 1, n);
}
inline void Modify(const int pos, const int x)
{
  _st = _ed = pos, _x = x;
  _modify(1, 1, n);
}

typedef int Array[MAXN];
Array size, top, hson, parent, number, depth;
void dfs(const int u)
{
  size[u] = 1;
  for (Edge *e = header[u]; e; e = e->next)
    if (e->v != parent[u])
    {
      parent[e->v] = u;
      depth[e->v] = depth[u]+1;
      dfs(e->v);
      size[u] += size[e->v];
      if (size[e->v] > size[hson[u]])
        hson[u] = e->v;
    }
}
void dfs2(const int u, const int tp)
{
  static int timestamp;
  number[u] = ++timestamp, top[u] = tp;
  if (hson[u])
    dfs2(hson[u], tp);
  for (Edge* e = header[u]; e; e = e->next)
    if (e->v != hson[u] && e->v != parent[u])
      dfs2(e->v, e->v);
}
int QMax(int a, int b)
{
  int ta = top[a], tb = top[b], res = QueryMax(number[a], number[a]);
  while (ta != tb)
  {
    if (depth[ta] < depth[tb])
      std::swap(ta, tb), std::swap(a, b);
    res = std::max(res, QueryMax(number[a], number[ta]));
    a = parent[ta], ta = top[a];
  }
  if (a == b) return res;
  if (depth[a] > depth[b]) std::swap(a, b);
  return std::max(res, QueryMax(number[a], number[b]));
}
int QSum(int a, int b)
{
  int ta = top[a], tb = top[b], res = 0;
  while (ta != tb)
  {
    if (depth[ta] < depth[tb])
      std::swap(ta, tb), std::swap(a, b);
    res += QuerySum(number[a], number[ta]);
    a = parent[ta], ta = top[a];
  }
  if (a == b) return res;
  if (depth[a] > depth[b]) std::swap(a, b);
  return res + QuerySum(number[a], number[b]);
}

int main()
{
  scanf("%d", &n);
  for (int i = 1, x, y; i < n; ++i)
  {
    scanf("%d%d", &x, &y);
    AddEdge(x, y);
    AddEdge(y, x);
  }
  dfs(1);
  dfs2(1, 1);
  for (int i = 0, x; i < n; ++i)
  {
    scanf("%d", &x);
    Modify(number[i+1], x);
  }
  scanf("%d", &m);
  for (int i = 0, x, y; i < m; ++i)
  {
    static char buf[10];
    scanf("\n%s%d%d", buf, &x, &y);
    switch (buf[1])
    {
      case 'M': printf("%d\n", QMax(x, y)); break;
      case 'S': printf("%d\n", QSum(x, y)); break;
      case 'H': Modify(number[x], y); break;
    }
  }
}

bzoj1146 树上第k大 LCA

这是唯一一题LCT无法做但是树链剖分可做的题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

#include <cstdio>
#include <algorithm>

const int MAXN = 80001, SQRTN = 283;
struct Edge { int v; Edge *next; };
Edge g[MAXN*2], *header[MAXN];
void AddEdge(const int x, const int y)
{
  static int LinkSize;
  Edge* const node = g+(LinkSize++);
  node->v = y;
  node->next = header[x];
  header[x] = node;
}

//-------Block Array:
int Blocks, Block[SQRTN][SQRTN], BSize[SQRTN], a[SQRTN*SQRTN];
int* lower_bound(int* const beg, int* const end, const int x)
{
  int* const pos = std::lower_bound(beg, end, x);
  return *pos != x ? pos-1 : std::upper_bound(beg, end, x)-1;
}
void BlockModify(const int index, const int value)
{
  const int block = index/SQRTN;
  const int offset = std::lower_bound(Block[block], Block[block]+BSize[block], a[index]) - Block[block];
  a[index] = Block[block][offset] = value;
  std::sort(Block[block], Block[block]+BSize[block]);
}
int BlockGetRank(const int st, const int ed, const int x)
{
  const int bs = st/SQRTN, be = ed/SQRTN;
  int rank = 0;
  if (bs == be)
  {
    for (int i = st; i <= ed; ++i) rank += a[i] <= x;
    return rank;
  }
  for (int i = st; i < (bs+1)*SQRTN; ++i) rank += a[i] <= x;
  for (int i = be*SQRTN; i <= ed; ++i) rank += a[i] <= x;
  for (int i = bs+1; i < be; ++i) rank += lower_bound(Block[i], Block[i]+BSize[i], x)-Block[i]+1;
  return rank;
}
int BlockGetMin()
{
  int res = 0x7FFFFFFF;
  for (int i = 0; i < Blocks; ++i)
    res = std::min(res, Block[i][0]);
  return res;
}
int BlockGetMax()
{
  int res = static_cast<int>(0x80000000);
  for (int i = 0; i < Blocks; ++i)
    res = std::max(res, Block[i][BSize[i]-1]);
  return res;
}
//-------Heavy-Light Decomposition:
typedef int Array[MAXN];
Array top, hson, parent, depth, size, number;
void HLDdfs(const int u)
{
  size[u] = 1, hson[u] = 0;
  for (Edge* e = header[u]; e; e = e->next)
    if (e->v != parent[u])
    {
      parent[e->v] = u;
      depth[e->v] = depth[u]+1;
      HLDdfs(e->v);
      size[u] += size[e->v];
      if (size[e->v] > size[hson[u]])
        hson[u] = e->v;
    }
}
void HLDdfs2(const int u, const int tp)
{
  static int timestamp;
  number[u] = timestamp++, top[u] = tp;
  if (hson[u])
    HLDdfs2(hson[u], tp);
  for (Edge *e = header[u]; e; e = e->next)
    if (e->v != hson[u] && e->v != parent[u])
      HLDdfs2(e->v, e->v);
}
int HLDGetRank(int a, int b, const int num, int& lca)
{
  int ta = top[a], tb = top[b], rank = 0;
  while (ta != tb)
  {
    if (depth[ta] < depth[tb])
      std::swap(ta, tb), std::swap(a, b);
    rank += BlockGetRank(number[ta], number[a], num);
    a = parent[ta], ta = top[a];
  }
  if (depth[a] > depth[b]) std::swap(a, b);
  lca = a;
  if (a == b) return rank + BlockGetRank(number[a], number[a], num);
  return rank + BlockGetRank(number[a], number[b], num);
}

int n, m, t[MAXN];
int main()
{
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i)
    scanf("%d", t+i);
  for (int i = 1, x, y; i < n; ++i)
  {
    scanf("%d%d", &x, &y);
    AddEdge(x, y);
    AddEdge(y, x);
  }
  HLDdfs(1);
  HLDdfs2(1, 1);
  for (int i = 1; i <= n; ++i)
    a[number[i]] = Block[number[i]/SQRTN][BSize[number[i]/SQRTN]++] = t[i];
  Blocks = 1+(n-1)/SQRTN;
  for (int i = 0; i < Blocks; ++i)
    std::sort(Block[i], Block[i]+BSize[i]);
  for (int i = 0, k, x, y; i < m; ++i)
  {
    scanf("%d%d%d", &k, &x, &y);
    if (k == 0)
    {
      BlockModify(number[x], y);
      continue;
    }
    int lef = BlockGetMin()-1, rig = BlockGetMax(), lca;
    HLDGetRank(x, y, 0, lca);
    const int nodes = depth[x]+depth[y]-depth[lca]*2+1;
    k = nodes-k+1;
    if (nodes < k || k < 1)
    {
      printf("invalid request!\n");
      continue;
    }
    while (rig-lef > 1)
    {
      const int mid = (lef+rig)/2;
      if (HLDGetRank(x, y, mid, lca) >= k)
        rig = mid;
      else
        lef = mid;
    }
    printf("%d\n", rig);
  }
}

bzoj2243 树上颜色统计

见http://oi.abcdabcd987.com/bzoj2243

为什么是HLD

因为树链剖分高端洋气的英文名叫做： Heavy-Light Decomposition

Comments