如何在O(N)时间复杂度下统计N叉树各节点的大于自身的后代节点数？

问题描述 #

给定一棵N叉树，节点数N范围为1 ≤ N ≤ 10^5，每个节点有一个值Vi（1 ≤ Vi ≤ 10^9）。需要输出每个节点的所有后代（含所有下层子节点）中值大于该节点的数量。

原代码采用每个节点单独遍历所有后代的方式，最坏时间复杂度为O(N²)，对于N=1e5的规模会严重超时，需要更高效的解决方案。

原代码问题分析 #

原代码对每个节点都发起一次深度优先遍历，逐个检查所有后代节点的值是否大于当前节点。当树为链状结构时，每个节点需要遍历O(N)个后代，总时间复杂度达到O(N²)，无法处理大规模数据。

最优解决方案思路 #

利用**欧拉序（Euler Tour）将树结构转化为区间问题，结合树状数组（Fenwick Tree）**进行离线统计：

1. 欧拉序标记：通过一次深度优先遍历，记录每个节点的进入时间in_time和离开时间out_time，此时每个节点的子树对应数组中[in_time[u], out_time[u]]的连续区间。
2. 离线排序处理：将所有节点按值从大到小排序，相同值的节点按进入时间从大到小排序（避免统计相同值的节点）。
3. 树状数组统计：按排序后的顺序处理节点，每次查询当前节点子树区间内已标记的节点数量（即比当前节点值大的后代数量），然后标记当前节点的位置。

这种方法的时间复杂度为O(N log N)，完全满足1e5规模的数据处理需求。

实现代码 #

import sys
sys.setrecursionlimit(1 << 25)

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)  # 1-based索引

    def update(self, idx, delta=1):
        while idx <= self.n:
            self.tree[idx] += delta
            idx += idx & -idx

    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def range_query(self, l, r):
        return self.query(r) - self.query(l - 1)

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    
    values = [0] * (N + 1)  # 1-based存储节点值
    for i in range(1, N + 1):
        values[i] = int(input[ptr])
        ptr += 1
    
    # 构建树结构
    tree = [[] for _ in range(N + 1)]
    for child in range(2, N + 1):
        parent = int(input[ptr])
        tree[parent].append(child)
        ptr += 1

    # 欧拉序记录节点的进入/离开时间
    in_time = [0] * (N + 1)
    out_time = [0] * (N + 1)
    time = 1
    def dfs(u):
        nonlocal time
        in_time[u] = time
        time += 1
        for v in tree[u]:
            dfs(v)
        out_time[u] = time - 1

    dfs(1)

    # 按节点值降序排序，值相同时按进入时间降序（避免统计同值节点）
    nodes = sorted([(i, values[i]) for i in range(1, N + 1)], 
                   key=lambda x: (-x[1], -in_time[x[0]]))

    ft = FenwickTree(N)
    result = [0] * (N + 1)

    for u, val in nodes:
        # 查询子树区间内已标记的节点数（即比当前节点值大的后代数量）
        cnt = ft.range_query(in_time[u], out_time[u])
        result[u] = cnt
        ft.update(in_time[u])

    # 按节点编号顺序输出结果
    for i in range(1, N + 1):
        print(result[i])

if __name__ == "__main__":
    main()

代码解释 #

1. FenwickTree类：实现树状数组的单点更新和区间查询功能，用于高效统计区间内已标记的节点数量。
2. 欧拉序遍历：通过DFS记录每个节点的进入和离开时间，将子树转化为连续区间，方便后续区间查询。
3. 离线排序：将节点按值从大到小排序，确保处理当前节点时，所有值更大的节点已经被标记，此时查询子树区间的标记数就是该节点的目标结果。
4. 结果统计：遍历排序后的节点，查询区间并更新树状数组，最后按节点编号输出结果。

内容的提问来源于stack exchange，提问作者dndn