树状数组练习题

这篇具有很好参考价值的文章主要介绍了树状数组练习题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

树状数组练习题

为什么大佬们一眼看出是树状数组呢？

不是一眼看出树状数组，而是要把 ~~【找两个相邻的最小值之间还有几个数没删掉】~~ 的问题转变成动态区间和问题，这个转化过程才是最重要的，至于你用什么数据结构求动态区间和是次要的，很多数据结构都能做，最常用的树状数组和线段树(这题比较特殊有序集合也能做)，树状数组容易套板，码量少，常数还比线段树小。所以你才会看到大佬们清一色的树状数组。

307. 区域和检索 - 数组可修改

难度中等602

给你一个数组 nums ，请你完成两类查询。

其中一类查询要求更新数组 nums 下标对应的值
另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（包含）的nums元素的和，其中 left <= right

实现 NumArray 类：

NumArray(int[] nums) 用整数数组 nums 初始化对象
void update(int index, int val) 将 nums[index] 的值更新为 val
int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（包含）的nums元素的和（即，nums[left] + nums[left + 1], ..., nums[right]）

示例 1：

输入：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]

解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

提示：

1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
调用 update 和 sumRange 方法次数不大于 3 * 104

class NumArray {

    BinaryIndexedTree t;
    int[] nums;

    public NumArray(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        t = new BinaryIndexedTree(n+1);
        for(int i = 0; i < n; i++){
            t.add(i+1, nums[i]);
        }
    }
    
    public void update(int index, int val) {
        t.add(index+1, val - nums[index]); // val - nums[index] :变化量
        nums[index] = val;
    }
    
    public int sumRange(int left, int right) {
        return t.query(right+1) - t.query(left);
    }
}
// 模板
class BinaryIndexedTree{
    private int n;
    private int[] tree;

    public BinaryIndexedTree(int n){ // 初始化时，要传入n+1
        this.n = n;
        tree = new int[n];
    }
    // 将index位置加上val值 arr[i] += val（注意传进来的index要+1）
    public void add(int index, int val){
        while(index < n){
            tree[index] += val;
            index += index & -index;
        }
    }
    // 查询[1, index]的前缀和（注意传进来的index要+1）
    public int query(int index) {
        int s = 0;
        while (index > 0) {
            s += tree[index];
            index -= index & -index; // n&(~n+1) == n&(-n)
        }
        return s;
    }
	// 返回[left, right]之间的区间和（注意传进来的index要+1）
    public int RangeSum(int left, int right){
        return query(right) - query(left-1);
    }
}

1626. 无矛盾的最佳球队

难度中等179

假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数总和。

然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。

给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。

示例 1：

输入：scores = [1,3,5,10,15], ages = [1,2,3,4,5]
输出：34
解释：你可以选中所有球员。

示例 2：

输入：scores = [4,5,6,5], ages = [2,1,2,1]
输出：16
解释：最佳的选择是后 3 名球员。注意，你可以选中多个同龄球员。

示例 3：

输入：scores = [1,2,3,5], ages = [8,9,10,1]
输出：6
解释：最佳的选择是前 3 名球员。

提示：

1 <= scores.length, ages.length <= 1000
scores.length == ages.length
1 <= scores[i] <= 106
1 <= ages[i] <= 1000

题解：注意更改了模板，类似线段树的区间修改，维护区间最大值（维护不超过当前球员年龄的球员的最大得分）

class Solution {
    public int bestTeamScore(int[] scores, int[] ages) {
        int n = ages.length;
        int[][] arr = new int[n][2];
        for(int i = 0; i < n; i++){
            arr[i] = new int[]{scores[i], ages[i]};
        }
        // 我们可以将球员按照分数从小到大排序，如果分数相同，则按照年龄从小到大排序。
        Arrays.sort(arr, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        int m = 0;
        for(int age : ages) m = Math.max(m, age);

        // 我们使用树状数组维护不超过当前球员年龄的球员的最大得分。
        BinaryIndexedTree tree = new BinaryIndexedTree(m+5);
        // 每一次，我们只需要在 O(logm) 的时间内找出不超过当前球员年龄的球员的最大得分，
        // 然后将当前球员的分数加到该得分上，即可更新当前球员年龄的最大得分。
        for(int[] x : arr){
            tree.add(x[1] + 1, x[0] + tree.query(x[1] + 1));
        }
        return tree.query(m+1);
    }
}

class BinaryIndexedTree{
    private int n;
    private int[] tree;

    public BinaryIndexedTree(int n){ // 初始化时，要传入n+1
        this.n = n;
        tree = new int[n];
    }
    // 将index位置加上val值 arr[i] += val（注意传进来的index要+1）
    public void add(int index, int val){
        while(index < n){
            tree[index] = Math.max(tree[index], val);
            index += index & -index;
        }
    }
    // 查询[1, index]的前缀和（注意传进来的index要+1）
    public int query(int index) {
        int s = 0;
        while (index > 0) {
            s = Math.max(tree[index], s);
            index -= index & -index; // n&(~n+1) == n&(-n)
        }
        return s;
    }
}

🎉6404. 将数组清空

难度困难2

给你一个包含若干 互不相同 整数的数组 nums ，你需要执行以下操作 直到****数组为空 ：

如果数组中第一个元素是当前数组中的 最小值 ，则删除它。
否则，将第一个元素移动到数组的末尾。

请你返回需要多少个操作使 nums 为空。

示例 1：

输入：nums = [3,4,-1]
输出：5

Operation	Array
1	[4, -1, 3]
2	[-1, 3, 4]
3	[3, 4]
4	[4]
5	[]

示例 2：

输入：nums = [1,2,4,3]
输出：5

Operation	Array
1	[2, 4, 3]
2	[4, 3]
3	[3, 4]
4	[4]
5	[]

示例 3：

输入：nums = [1,2,3]
输出：3

Operation	Array
1	[2, 3]
2	[3]
3	[]

提示：

1 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 中的元素 互不相同 。

题解：小羊肖恩 https://leetcode.cn/u/yawn_sean/

首先，我们肯定不能直接执行题目中给出的操作，否则时间复杂度将达到操作的数量。那么，我们应该在原数组中考虑删除操作和移动操作分别意味着什么。

我们考虑一个指针，在原数组中进行移动，且每次移动一个单位。那么“第一个元素移动到末尾”可以刻画为将该指针移动到下一个还在数组中的数字位置上，“删除”可以刻画为将某一个位置置空。

删除的位置顺序是预先给定的，对应位置的数字从小到大。

接下来我们考虑两次删除操作之间的间隔，相当于从某个位置移动到下一个最小值的位置。这两个位置在原数组中的下标是确定的， 因此我们只需要考虑这两点间有多少位置未被置空即可，这相当于一个区间求和，每次可以更新置空情况。 这可以通过线段树或树状数组等实现（可以搜索相关知识）。具体逻辑可见代码注释。

时间复杂度为O(nlogn)，来源于排序还有树状数组等结构的更新

为什么大佬们一眼看出是树状数组呢？

不是一眼看出树状数组，而是要把找两个相邻的最小值之间还有几个数没删掉的问题转变成动态区间和问题，这个转化过程才是最重要的，至于你用什么数据结构求动态区间和是次要的，很多数据结构都能做，最常用的树状数组和线段树(这题比较特殊有序集合也能做)，树状数组容易套板，码量少，常数还比线段树小。所以你才会看到大佬们清一色的树状数组。

树状数组解法：

题解：https://leetcode.cn/problems/make-array-empty/solution/shu-zhuang-shu-zu-mo-ni-pythonjavacgo-by-ygvb/文章来源地址https://www.toymoban.com/news/detail-437043.html

class Solution:
    """
    转换：
    将第一个元素移动到数组的末尾 
        ==> 用 下标  来标记当前数组的第一个数是谁，然后不断往后移动
            举例 ：2413 ==> 当前下标2 ==> 1324 ==>删除1 ==> 324 ==> 当前下标3
    这个转换是怎么想到的？技巧，相对关系【数字往后移 等价于 用一个下标来模拟】

    删除一个数后，下标自动向右移动一位（这一次操作是免费的）

    我们需要记录每一个数的位置，从小到大删除
    上一个删除的数的下标是 pre， 当前要删除的下标是 i
    因此我们需要思考【从pre移动到i，需要移动多少次？】
    1. 维护中间被删除的数字个数
    ==> 树状数组
        如果pre <= i, 移动次数 i-pre-query(pre,i) 【pre到i，再减去中间删除的个数】
        如果pre > i, 移动次数 n - pre-query(pre,n) + 1【n到1的那一步】 + (i-1) - query(1,i) 【pre到n，再从1到i】 
            简化一下： n - pre + i - (k - query(i, pre-1)) 【树状数组中一共有k个数】
    2. 

    """
    def countOperationsToEmptyArray(self, nums: List[int]) -> int:
        ans = n = len(nums) # 先把 n 计入答案
        t = BIT(n+1) # 树状数组下标从1开始
        pre = 1 # 上一个最小值的位置，初始为 1
        # 根据元素大小对下标进行排序，然后枚举 数的位置 从小到大删除每个数
        ids = sorted(range(n), key = lambda i: nums[i])
        for k, i in enumerate(ids):
            i += 1 # 下标i从1开始
            if pre <= i: # 从 pre 移动到 i，跳过已经删除的数
                ans += i - pre - t.query(pre, i)
            else:
                ans += n - pre + i - (k - t.query(i, pre-1))
            t.inc(i) # 删除i（添加到树状数组中）
            pre = i
        return ans

# 树状数组模板
class BIT:
    def __init__(self, n):
        self.tree = [0] * n

    # 将下标 i 上的数加一
    def inc(self, i: int) -> None:
        while i < len(self.tree):
            self.tree[i] += 1
            i += i & -i

    # 返回闭区间 [1, i] 的元素和
    def sum(self, i: int) -> int:
        res = 0
        while i > 0:
            res += self.tree[i]
            i &= i - 1
        return res

    # 返回闭区间 [left, right] 的元素和
    def query(self, left: int, right: int) -> int:
        return self.sum(right) - self.sum(left - 1)