一、引言

LeetCode 3161 块放置查询是区间动态维护与高效查询的典型问题，核心需求是在数轴上动态添加障碍物，并快速判断指定位置左侧是否存在足够长的连续空白区间。

在众多解法中，树状数组（Fenwick Tree） 凭借其实现极简、常数更小、空间更省的优势，负责维护前缀区间的最大空白长度；而并查集（Union-Find） 则通过路径压缩，在倒序处理的场景下以近似 O (1) 的复杂度快速找到左右最近障碍物的位置。两者结合，完美匹配本题的能力边界，是本题的高效解法之一。

本文将从问题本质出发，结合并查集与最大值树状数组，给出一套逻辑清晰、可直接提交的 Java 代码，帮助你彻底掌握树状数组与并查集在区间维护类问题中的组合应用技巧。

开始之前，大家也可以先去看一下线段树的解法

力扣 3161. 块放置查询：线段树解法（Java 实现）-CSDN博客

二、树状数组

2.1 定义

树状数组是一种：用数组模拟、依靠二进制规律实现的、专门处理 单点更新 + 前缀查询 的高效数据结构。

树状数组只有且仅有两个核心操作：

① 单点更新

修改数组中某一个位置的值时间 O (logN)

② 前缀查询

求 1 ~ x 的总和 / 最大值时间 O (logN)

2.2 i 管理的区

间长度 = lowbit (i)

lowbit (i) = 数字 i 在二进制里，最右边的 1 代表的值

lowbit(i) = i & -i（二进制最右边的 1）

6 → 0000 0110

-6（取反 +1）

  1. 取反：1111 1001
  2. 加 1：1111 1010
  0000 0110
& 1111 1010
-------------
  0000 0010

6 管理 [ 5 ,  6 ]

把下标按二进制位分层聚合，每个节点只负责以自己结尾、长度为 lowbit (i) 的连续段。

这种划分天然匹配二进制进位，让查询、更新都能沿着二进制位跳跃。

2.3 单点更新

改一个点 → 只改所有包含它的大块 → 跳 log (n) 次就结束

我要把 第 3 个数 +5

c [3] (3)包含 3 ✔

c [4] (1- 4)包含 3 ✔ （3 + 1【lowbit（3）】）

c [8] (1 - 8)包含 3 ✔ （4 + 4【lowbit（4）】）

c[x] = [x - lowbit(x) + 1 , x]

c[x + lowbit(x)] = [ x + lowbit(x) - lowbit(x + lowbit(x)) + 1 , x + lowbit(x)]

lowbit(x)是x最右边的1，那么x + lowbit（x） 就会让x进1，

lowbit（x + lowbit（x））>= 2 * lowbit(x)

x + lowbit(x) - lowbit(x + lowbit(x)) + 1  <= x + lowbit(x) - 2 * lowbit(x) + 1 = x - lowbit(x) + 1

所以c[x + lowbit(x)]  一定包含x

2.4 前缀和查询

求 1+2+3+4+5+6

步骤：拼出 1~6

从 6 开始往前跳：

  1. 6 管 [5,6] → 加 c [6]
  2. 6 - 2 = 4 管 [1,2,3,4] → 加 c [4]
  3. 4 - 4 = 0 → 结束

总和 = c[6] + c[4]

因为c[x]只管[x - lowbit(x) + 1 , x]

所以要往下减,设y = x - lowbit(x) c[ y ] = [y - lowbit(y) + 1 , y]

不断往下减，直到为0

2.5 代码实现

public class FenwickTree {
    private int[] tree;
    private int n;

    // 初始化：大小为 size 的树状数组
    public FenwickTree(int size) {
        this.n = size;
        tree = new int[n + 1]; // 注意：树状数组下标从 1 开始！
    }

    // ------------------- 核心1：lowbit -------------------
    private int lowbit(int x) {
        return x & -x;
    }

    // ------------------- 核心2：单点更新 -------------------
    // 给下标 idx 的位置 +val
    public void update(int idx, int val) {
        for (; idx <= n; idx += lowbit(idx)) {
            tree[idx] += val;
        }
    }

    // ------------------- 核心3：前缀和查询 -------------------
    // 查询 [1 ... idx] 的和
    public int query(int idx) {
        int res = 0;
        for (; idx > 0; idx -= lowbit(idx)) {
            res += tree[idx];
        }
        return res;
    }

    // ------------------- 扩展：区间和查询 -------------------
    // 查询 [l ... r] 的和
    public int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
}

三、树状数组解法

3.1 与线段树区别

关于线段树可以先看我的这篇博客来了解

力扣 3161. 块放置查询：线段树解法（Java 实现）-CSDN博客

对比项 树状数组 线段树
代码量 极短，模板固定，易写不易错 更长，递归 + 区间划分，还要掌握懒标记
常数效率 更高，循环遍历，无递归开销 略低，递归调用有额外开销
下标要求 必须从 1 开始 0/1 均可，更灵活
单点更新 ✅ 擅长 ✅ 支持
前缀查询 ✅ 原生最强 ✅ 支持
任意区间和 ✅ 前缀相减实现 ✅ 原生支持
任意区间最值 ❌ 不支持 ✅ 原生支持
区间批量更新 ❌ 需差分变通 ✅ 懒标记原生支持
区间结构合并（连续段等） ❌ 不支持 ✅ 核心能力

3.2 思路

每次查询：在 0 ~ x 之间，最大的空隙是多少？

这个就是求前缀，非常适合树状数组

线段树 = 什么区间都能查

这里我们来引入倒序的思想，在线段树中我们是先插入屏障再去查询，此时我们的最大连续间隔一定会越来越小。我们也可以倒着来，先把所有的屏障都插好，然后倒叙不断查询，拔出屏障，最大连续间隔会变得越来越大！

3.3 代码实现

class Solution {
    public static class FenwickTree{
        private int[] tree;
        private int size;

        public FenwickTree(int size){
            this.size = size;
            this.tree = new int[size];
        }

        private int lowbit(int x){
            // 6:0110 -6:1010(1001 + 1) 6 & -6 = 0010 = 4
            // 获得x右边第一位1
            return x & -x;
        }

        private void update(int x , int val){
            // 寻找tree[x]的父区域
            // tree[x] : x - lowbit(x) + 1 ~ x
            // tree[x + lowbit(x)] : x + lowbit(x) - lowbit(x + lowbit(x)) + 1 ~ x + lowbit(x)
            // lowbit(x + lowbit(x)) >= 2 * lowbit(x)
            // x + lowbit(x) - lowbit(x + lowbit(x)) + 1 <= x - lowbit(x) + 1
            // tree[x + lowbit(x)]一定包含x，需要更新
            for ( ; x < size ; x += lowbit(x)){
                // 因为我们是倒序的，拔出屏障，所以最大空白区域只会多，不会少，用max
                // 如果是第一次插入的话，由于原来是0，也会直接取新的（并且是按照从小到大的顺序插入的）
                tree[x] = Math.max(tree[x] , val);
            }
        }

        private int query(int x){
            int res = 0;
            // tree[x] : x - lowbit(x) + 1 ~ x
            // tree[x - lowbit(x)] : x - lowbit(x) - lowbit(x - lowbit(x)) + 1 ~ x - lowbit(x)
            // 这些区间连续起来就是我们要查询的区间
            for (; x > 0 ; x -= lowbit(x)){
                // 因为我们要求的是最大空白区域，所以直接max就好了
                // 相加的是前缀和
                res = Math.max(res , tree[x]);
            }
            return res;
        }
    }

    public List<Boolean> getResults(int[][] queries) {
        int max = 0;
        // list方便遍历
        List<Integer> position = new ArrayList<>();
        position.add(0);
        for (int[] query : queries){
            max = Math.max(max , query[1]);
            if (query[0] == 1){
                position.add(query[1]);
            }
        }
        // max还需要加1，因为直接当作屏障的话，ceiling会有问题
        max++;
        // 0 , max作为两个哨兵，作为左右的天然屏障
        position.add(max);
        Collections.sort(position);
        // treeset方便查找上下屏障
        TreeSet<Integer> set = new TreeSet<>(position);
        FenwickTree tree = new FenwickTree(max);
        for (int i = 1 ; i < position.size() ; i++){
            tree.update(position.get(i) , position.get(i) - position.get(i - 1));
        }
        List<Boolean> res = new ArrayList<>();
        for (int i = queries.length - 1 ; i >= 0 ; i--){
            int[] query = queries[i];
            int x = query[1];
            // 查找左边的障碍
            int pre = set.floor(x - 1);
            if (query[0] == 1){
                // 倒序遍历，拔出屏障
                set.remove(x);
                int next = set.ceiling(x);
                tree.update(next , next - pre);
            } else {
                // 这里注意不要头插，会超时
                res.add(Math.max(tree.query(pre) , x - pre) >= query[2]);
            }
        }
        Collections.reverse(res);
        return res;
    }
}

四、并查集优化

4.1 并查集

并查集是一种处理元素分组、集合合并、查询元素是否同组的高效数据结构，核心就两个操作：合并、查找。

把一堆元素划分成若干互不相交的集合：

  1. 每个集合选一个根节点代表整个集合；
  2. 判断两个元素是否同组 → 找各自根节点，根相同则同组；
  3. 把两个集合合并 → 让一个集合的根指向另一个集合的根。

4.2 代码实现

class UnionFind {
    int[] parent;

    // 初始化
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) 
            parent[i] = i;
    }

    // 路径压缩 
    public int find(int x) {
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    }

    // 合并
    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}

五、并查集解法

5.1 思路

之前我们是用 TreeSet（有序集合） 快速找左右最近障碍物，但是现在我们可以用 并查集（UnionFind） 快速找左右最近障碍物

特性 TreeSet 版 并查集版
代码难度 简单，易写易读 较难，思路更巧妙
运行速度 较快 O(logn) 极快 近似 O(1)
数据量极大时 可能略慢 优势明显
代码量 少 多（多了并查集类）

那么我们接下里可以搞一个左边的最近障碍物和右边的最近障碍物

5.2 代码实现

class Solution {
    public static class FenwickTree{
        private int[] tree;
        private int size;

        public FenwickTree(int size){
            this.size = size;
            this.tree = new int[size];
        }

        private int lowbit(int x){
            // 6:0110 -6:1010(1001 + 1) 6 & -6 = 0010 = 4
            // 获得x右边第一位1
            return x & -x;
        }

        private void update(int x , int val){
            // 寻找tree[x]的父区域
            // tree[x] : x - lowbit(x) + 1 ~ x
            // tree[x + lowbit(x)] : x + lowbit(x) - lowbit(x + lowbit(x)) + 1 ~ x + lowbit(x)
            // lowbit(x + lowbit(x)) >= 2 * lowbit(x)
            // x + lowbit(x) - lowbit(x + lowbit(x)) + 1 <= x - lowbit(x) + 1
            // tree[x + lowbit(x)]一定包含x，需要更新
            for ( ; x < size ; x += lowbit(x)){
                // 因为我们是倒序的，拔出屏障，所以最大空白区域只会多，不会少，用max
                // 如果是第一次插入的话，由于原来是0，也会直接取新的（并且是按照从小到大的顺序插入的）
                tree[x] = Math.max(tree[x] , val);
            }
        }

        private int query(int x){
            int res = 0;
            // tree[x] : x - lowbit(x) + 1 ~ x
            // tree[x - lowbit(x)] : x - lowbit(x) - lowbit(x - lowbit(x)) + 1 ~ x - lowbit(x)
            // 这些区间连续起来就是我们要查询的区间
            for (; x > 0 ; x -= lowbit(x)){
                // 因为我们要求的是最大空白区域，所以直接max就好了
                // 相加的是前缀和
                res = Math.max(res , tree[x]);
            }
            return res;
        }
    }

    public static class UnionFind{
        int[] father;

        public UnionFind(int size){
            father = new int[size];
            for (int i = 1 ; i < size ; i++){
                father[i] = i;
            }
        }

        private int find(int x){
            return (father[x] == x) ? x : (father[x] = find(father[x]));
        }
    }

    public List<Boolean> getResults(int[][] queries) {
        int max = 0;
        // list方便遍历
        List<Integer> position = new ArrayList<>();
        position.add(0);
        for (int[] query : queries){
            max = Math.max(max , query[1]);
            if (query[0] == 1){
                position.add(query[1]);
            }
        }
        // max还需要加1，因为直接当作屏障的话，ceiling会有问题
        max++;
        // 0 , max作为两个哨兵，作为左右的天然屏障
        position.add(max);
        Collections.sort(position);
        // 这里要+1是因为father的索引从1开始
        UnionFind left = new UnionFind(max + 1);
        UnionFind right = new UnionFind(max + 1);
        FenwickTree tree = new FenwickTree(max);
        for (int i = 1 ; i < position.size() ; i++){
            int cur = position.get(i);
            int pre = position.get(i - 1);
            tree.update(cur , cur - pre);
            for (int j = pre + 1 ; j < cur ; j++){
                left.father[j] = pre;
                right.father[j] = cur;
            }
        }
        List<Boolean> res = new ArrayList<>();
        for (int i = queries.length - 1 ; i >= 0 ; i--){
            int[] query = queries[i];
            int x = query[1];
            // 查找左边的障碍
            int pre = left.find(x - 1);
            if (query[0] == 1){
                // 倒序遍历，拔出屏障
                // 这里会直接find到最终的障碍处
                left.father[x] = x - 1;
                right.father[x] = x + 1;
                int next = right.find(x);
                tree.update(next , next - pre);
            } else {
                // 这里注意不要头插，会超时
                res.add(Math.max(tree.query(pre) , x - pre) >= query[2]);
            }
        }
        Collections.reverse(res);
        return res;
    }
}

# 算法 # java # 开发语言 # leetcode
Logo
亚马逊云科技技术品牌专区

更多推荐

虚拟化技术深度解析：从底层原理到产业实践，读懂云计算的核心基石

文章摘要 虚拟化技术作为云计算的核心基础，经历了从大型机到云原生的演进历程。本文系统梳理了虚拟化的技术脉络：从解决物理机资源浪费的初衷出发，阐述了Hypervisor的资源隔离原理，对比了TypeI和TypeII两种架构特性，并深入分析了KVM、Docker等典型技术方案。虚拟化的本质是对计算资源的抽象，通过屏蔽硬件细节实现灵活调度。文章最后以OpenStack私有云搭建为例展示了虚拟化实践，并指

avatar 亚马逊云科技技术品牌专区
cover

大数据相关专业，优先选城市还是学校？

avatar 亚马逊云科技技术品牌专区

从基础到应用架构系列-云计算的概念

云计算”这个词，我想大伙肯定听过不止一次了，但是可能我们经常会被同行的同事或者业界的朋友问道，什么是云计算，云计算是干什么的？可能让我们去跟他们解释的时候，我们并不是很容易的把这个词语解释的很清楚或者很形象，为什么，可能是因为我们对云计算本身的概念不是特别的清晰，或者，由于我们没有深入的了解和使用云计算的原因吧，或者还有其他方面的原因，本文是通过一些小的场景来说明云计算的概念，这个概念呢，其实也不

avatar 亚马逊云科技技术品牌专区