关于各类「区间和」问题如何选择解决方案(含模板)| Java 刷题打卡

简介: 关于各类「区间和」问题如何选择解决方案(含模板)| Java 刷题打卡

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 307. 区域和检索 - 数组可修改 ,难度为 中等


Tag : 「区间和」、「树状数组」


给你一个数组 nums ,请你完成两类查询,其中一类查询要求更新数组下标对应的值,另一类查询要求返回数组中某个范围内元素的总和。


实现 NumArray 类:


  • NumArray(int[] nums) 用整数数组 nums 初始化对象
  • void update(int index, int val) 将 nums[index] 的值更新为 val
  • int sumRange(int left, int right) 返回子数组 nums[left, right] 的总和(即,nums[left] + nums[left + 1], ..., nums[right])


示例:


输入:
["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); // 返回 9 ,sum([1,3,5]) = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 8 ,sum([1,2,5]) = 8
复制代码


提示:


  • 1 <= nums.length <= 3 * 10^4104
  • -100 <= nums[i] <= 100
  • 0 <= index < nums.length
  • -100 <= val <= 100
  • 0 <= left <= right < nums.length
  • 最多调用 3 * 10^4104 次 update 和 sumRange 方法


解题思路



这是一道很经典的题目,通常还能拓展出一大类问题。


针对不同的题目,我们有不同的方案可以选择(假设我们有一个数组):


  1. 数组不变,求区间和:「前缀和」、「树状数组」、「线段树」
  2. 多次修改某个数,求区间和:「树状数组」、「线段树」
  3. 多次整体修改某个区间,求区间和:「线段树」、「树状数组」(看修改区间的数据范围)
  4. 多次将某个区间变成同一个数,求区间和:「线段树」、「树状数组」(看修改区间的数据范围)


这样看来,「线段树」能解决的问题是最多的,那我们是不是无论什么情况都写「线段树」呢?


答案并不是,而且恰好相反,只有在我们遇到第 4 类问题,不得不写「线段树」的时候,我们才考虑线段树。


因为「线段树」代码很长,而且常数很大,实际表现不算很好。我们只有在不得不用的时候才考虑「线段树」。


总结一下,我们应该按这样的优先级进行考虑:


  1. 简单求区间和,用「前缀和」
  2. 多次将某个区间变成同一个数,用「线段树」
  3. 其他情况,用「树状数组」


树状数组



本题显然属于第 2 类问题:多次修改某个数,求区间和。


我们使用「树状数组」进行求解。


「树状数组」本身是一个很简单的数据结构,但是要搞懂其为什么可以这样「查询」&「更新」还是比较困难的(特别是为什么可以这样更新),往往需要从「二进制分解」进行出发理解。


因此我这里直接提供「树状数组」的代码,大家可以直接当做模板背过即可。


代码:


class NumArray {
    int[] tree;
    int lowbit(int x) {
        return x & -x;
    }
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];
        return ans;
    }
    void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) tree[i] += u;
    }
    int[] nums;
    int n;
    public NumArray(int[] _nums) {
        nums = _nums;
        n = nums.length;
        tree = new int[n + 1];
        for (int i = 0; i < n; i++) add(i + 1, nums[i]);
    }
    public void update(int i, int val) {
        add(i + 1, val - nums[i]);
        nums[i] = val;
    }
    public int sumRange(int l, int r) {
        return query(r + 1) - query(l);
    }
}
复制代码


  • 时间复杂度:add 操作和 query 的复杂度都是 O(\log{n})O(logn),因此构建数组的复杂度为 O(n\log{n})O(nlogn)。整体复杂度为 O(n\log{n})O(nlogn)
  • 空间复杂度:O(n)O(n)


树状数组模板



代码:


// 上来先把三个方法写出来
{
    int[] tree;
    int lowbit(int x) {
        return x & -x;
    }
    // 查询前缀和的方法
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];
        return ans;
    }
    // 在树状数组 x 位置中增加值 u
    void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) tree[i] += u;
    }
}
// 初始化「树状数组」,要默认数组是从 1 开始
{
    for (int i = 0; i < n; i++) add(i + 1, nums[i]);
}
// 使用「树状数组」:
{   
    void update(int i, int val) {
        // 原有的值是 nums[i],要使得修改为 val,需要增加 val - nums[i]
        add(i + 1, val - nums[i]); 
        nums[i] = val;
    }
    int sumRange(int l, int r) {
        return query(r + 1) - query(l);
    }
}
复制代码


最后



这是我们「刷穿 LeetCode」系列文章的第 No.307 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:

github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
12天前
|
存储 NoSQL 算法
实现分布式锁的Java解决方案
实现分布式锁的Java解决方案
|
15天前
|
安全 Java Apache
Java中的单点登录(SSO)解决方案
Java中的单点登录(SSO)解决方案
|
15天前
|
缓存 安全 Java
Java中的线程安全问题及解决方案
Java中的线程安全问题及解决方案
|
9天前
|
消息中间件 Java 中间件
Java面试题:解释分布式事务的概念,讨论常见的分布式事务解决方案。
Java面试题:解释分布式事务的概念,讨论常见的分布式事务解决方案。
14 0
|
9天前
|
设计模式 安全 Java
Java面试题:请列举三种常用的设计模式,并分别给出在Java中的应用场景?请分析Java内存管理中的主要问题,并提出相应的优化策略?请简述Java多线程编程中的常见问题,并给出解决方案
Java面试题:请列举三种常用的设计模式,并分别给出在Java中的应用场景?请分析Java内存管理中的主要问题,并提出相应的优化策略?请简述Java多线程编程中的常见问题,并给出解决方案
17 0
|
11天前
|
存储 NoSQL 算法
实现分布式锁的Java解决方案
实现分布式锁的Java解决方案
|
11天前
|
Java 调度
Java并发编程中的常见陷阱及解决方案
Java并发编程中的常见陷阱及解决方案
|
12天前
|
消息中间件 Java 数据库
实现Java中的分布式事务管理的挑战与解决方案
实现Java中的分布式事务管理的挑战与解决方案
|
16天前
|
缓存 安全 Java
Java中的线程安全问题及解决方案
Java中的线程安全问题及解决方案
|
17天前
|
安全 Java 开发者
Java并发编程中的线程安全问题及解决方案探讨
在Java编程中,特别是在并发编程领域,线程安全问题是开发过程中常见且关键的挑战。本文将深入探讨Java中的线程安全性,分析常见的线程安全问题,并介绍相应的解决方案,帮助开发者更好地理解和应对并发环境下的挑战。【7月更文挑战第3天】