标签： 树状数组

3161.物块放置查询

目标

有一条无限长的数轴，原点在 0 处，沿着 x 轴 正 方向无限延伸。

给你一个二维数组 queries ，它包含两种操作：

  1. 操作类型 1 ：queries[i] = [1, x] 。在距离原点 x 处建一个障碍物。数据保证当操作执行的时候，位置 x 处 没有 任何障碍物。
  2. 操作类型 2 ：queries[i] = [2, x, sz] 。判断在数轴范围 [0, x] 内是否可以放置一个长度为 sz 的物块，这个物块需要 完全 放置在范围 [0, x] 内。如果物块与任何障碍物有重合，那么这个物块 不能 被放置，但物块可以与障碍物刚好接触。注意，你只是进行查询，并 不是 真的放置这个物块。每个查询都是相互独立的。

请你返回一个 boolean 数组results ，如果第 i 个操作类型 2 的操作你可以放置物块，那么 results[i] 为 true ，否则为 false 。

示例 1：

输入：queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]
输出：[false,true,true]
解释：
查询 0 ，在 x = 2 处放置一个障碍物。在 x = 3 之前任何大小不超过 2 的物块都可以被放置。

示例 2：

输入：queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]
输出：[true,true,false]
解释：
查询 0 在 x = 7 处放置一个障碍物。在 x = 7 之前任何大小不超过 7 的物块都可以被放置。
查询 2 在 x = 2 处放置一个障碍物。现在，在 x = 7 之前任何大小不超过 5 的物块可以被放置，x = 2 之前任何大小不超过 2 的物块可以被放置。

说明：

  • 1 <= queries.length <= 15 * 10^4
  • 2 <= queries[i].length <= 3
  • 1 <= queries[i][0] <= 2
  • 1 <= x, sz <= min(5 10^4, 3 queries.length)
  • 输入保证操作 1 中，x 处不会有障碍物。
  • 输入保证至少有一个操作类型 2 。

思路

代码

性能

3660.跳跃游戏IX

目标

给你一个整数数组 nums。

从任意下标 i 出发，你可以根据以下规则跳跃到另一个下标 j：

  • 仅当 nums[j] < nums[i] 时，才允许跳跃到下标 j，其中 j > i。
  • 仅当 nums[j] > nums[i] 时，才允许跳跃到下标 j，其中 j < i。

对于每个下标 i，找出从 i 出发且可以跳跃 任意 次，能够到达 nums 中的 最大值 是多少。

返回一个数组 ans，其中 ans[i] 是从下标 i 出发可以到达的最大值。

示例 1:

输入: nums = [2,1,3]
输出: [2,2,3]
解释:
对于 i = 0：没有跳跃方案可以获得更大的值。
对于 i = 1：跳到 j = 0，因为 nums[j] = 2 大于 nums[i]。
对于 i = 2：由于 nums[2] = 3 是 nums 中的最大值，没有跳跃方案可以获得更大的值。
因此，ans = [2, 2, 3]。

示例 2:

输入: nums = [2,3,1]
输出: [3,3,3]
解释:
对于 i = 0：向后跳到 j = 2，因为 nums[j] = 1 小于 nums[i] = 2，然后从 i = 2 跳到 j = 1，因为 nums[j] = 3 大于 nums[2]。
对于 i = 1：由于 nums[1] = 3 是 nums 中的最大值，没有跳跃方案可以获得更大的值。
对于 i = 2：跳到 j = 1，因为 nums[j] = 3 大于 nums[2] = 1。
因此，ans = [3, 3, 3]。

说明:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

思路

有一个整数数组 nums，从任意下标 i 出发，可以向后跳到比 nums[i] 小的位置，向前跳到比 nums[i] 大的位置。返回从每一个下标 i 出发跳跃任意次能够到达的 nums 中的最大值。

定义 dp[i] 表示下标 i 所能到达的最大值，记录前缀最大值 preMax 与后缀最小值 suffixMin。如果 preMax[i + 1] <= suffixMin[i + 1]，dp[i] = preMax[i + 1]，否则 dp[i] = dp[i + 1]。

// todo: 树状数组 线段树 单调栈解法

代码


/**
 * @date 2026-05-07 14:41
 */
public class MaxValue3660 {

    public int[] maxValue(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] preMax = new int[n + 1];
        for (int i = 0; i < n; i++) {
            preMax[i + 1] = Math.max(preMax[i], nums[i]);
        }
        int suffixMin = nums[n - 1];
        dp[n - 1] = preMax[n];
        for (int i = n - 2; i >= 0; i--) {
            if (preMax[i + 1] <= suffixMin) {
                dp[i] = preMax[i + 1];
            } else {
                dp[i] = dp[i + 1];
            }
            suffixMin = Math.min(suffixMin, nums[i]);
        }
        return dp;
    }

}

性能

2179.统计数组中好三元组数目

目标

给你两个下标从 0 开始且长度为 n 的整数数组 nums1 和 nums2 ，两者都是 [0, 1, ..., n - 1] 的 排列 。

好三元组 指的是 3 个 互不相同 的值，且它们在数组 nums1 和 nums2 中出现顺序保持一致。换句话说，如果我们将 pos1v 记为值 v 在 nums1 中出现的位置，pos2v 为值 v 在 nums2 中的位置，那么一个好三元组定义为 0 <= x, y, z <= n - 1 ，且 pos1x < pos1y < pos1z 和 pos2x < pos2y < pos2z 都成立的 (x, y, z) 。

请你返回好三元组的 总数目 。

示例 1：

输入：nums1 = [2,0,1,3], nums2 = [0,1,2,3]
输出：1
解释：
总共有 4 个三元组 (x,y,z) 满足 pos1x < pos1y < pos1z ，分别是 (2,0,1) ，(2,0,3) ，(2,1,3) 和 (0,1,3) 。
这些三元组中，只有 (0,1,3) 满足 pos2x < pos2y < pos2z 。所以只有 1 个好三元组。

示例 2：

输入：nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
输出：4
解释：总共有 4 个好三元组 (4,0,3) ，(4,0,2) ，(4,1,3) 和 (4,1,2) 。

说明：

  • n == nums1.length == nums2.length
  • 3 <= n <= 10^5
  • 0 <= nums1[i], nums2[i] <= n - 1
  • nums1 和 nums2 是 [0, 1, ..., n - 1] 的排列。

提示：

  • For every value y, how can you find the number of values x (0 ≤ x, y ≤ n - 1) such that x appears before y in both of the arrays?
  • Similarly, for every value y, try finding the number of values z (0 ≤ y, z ≤ n - 1) such that z appears after y in both of the arrays.
  • Now, for every value y, count the number of good triplets that can be formed if y is considered as the middle element.

思路

有两个 0 ~ n - 1 的排列，好三元组指这两个排列的公共子序列，求好三元组的总数目。

// todo

代码

性能

Binary Indexed Tree / Fenwick Tree

树状数组（Binary Indexed Tree，也称为Fenwick Tree）作为一种高效的数据结构，主要用于区间查询和动态更新数据。

Fenwick Tree（芬威克树）得名于其发明者 Peter M. Fenwick（彼得·梅隆·芬威克），一位计算机科学家。他在1994年首次提出了这种数据结构，并以论文"A New Data Structure for Cumulative Frequency Tables" 的形式发表了这一成果。因为这种数据结构在处理累积频率表和其他区间查询问题上表现出了高效性，所以后来人们便以他的姓氏 Fenwick 来命名，以表彰他的贡献。

以下是论文摘要

A new method (the ‘binary indexed tree’) is presented for maintaining the cumulative frequencies which are needed to support dynamic arithmetic data compression. It is based on a decomposition of the cumulative frequencies into portions which parallel the binary representation of the index of the table element (or symbol). The perations to traverse the data structure are based on the binary coding of the index. In comparison with previous methods, the binary indexed tree is faster, using more compact data and simpler code. The access time for all operations is either constant or proportional to the logarithm of the table size. In conjunction with the compact data structure, this makes the new method particularly suitable for large symbol alphabets.