【leetcode难题】2569. 更新数组后处理求和查询【线段树实现01翻转和区间求和模版】

这篇具有很好参考价值的文章主要介绍了【leetcode难题】2569. 更新数组后处理求和查询【线段树实现01翻转和区间求和模版】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目截图

【leetcode难题】2569. 更新数组后处理求和查询【线段树实现01翻转和区间求和模版】,leetcode,算法,职场和发展文章来源地址https://www.toymoban.com/news/detail-614891.html

题目分析

  • 关键就是记录每次操作2时,nums1中的1的个数
  • 这就需要实现线段树进行区间反转以及区间求和

ac code

class Solution:
    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums1)
        m = len(queries)
        seg_tree = SegTree(nums1)

        # 只需要记录每次2操作时nums1中有多少个1即可
        total = sum(nums2)
        ans = []
        for i in range(m):
            if queries[i][0] == 1:
                l = queries[i][1]
                r = queries[i][2]
                seg_tree.reverse_range(l, r)
            elif queries[i][0] == 2:
                total += seg_tree.sum_range(0, n - 1) * queries[i][1]
            elif queries[i][0] == 3:
                ans.append(total)
        return ans


class SegTree:
    def __init__(self, nums):
        n = len(nums)
        self.arr = [SegNode() for _ in range(n * 4 + 1)]
        self.build(1, 0, n - 1, nums)

    def sum_range(self, left, right):
        return self.query(1, left, right)

    def reverse_range(self, left, right):
        self.modify(1, left, right)

    def build(self, id, l, r, nums):
        arr = self.arr
        arr[id] = SegNode()
        arr[id].l = l
        arr[id].r = r
        arr[id].lazytag = False
        if l == r:
            arr[id].sum = nums[l]
            return
        mid = (l + r) >> 1
        self.build(2 * id, l, mid, nums)
        self.build(2 * id + 1, mid + 1, r, nums)
        arr[id].sum = arr[2 * id].sum + arr[2 * id + 1].sum

    # pushdown函数:下传懒标记,即将当前区间的修改情况下传到其左右孩子结点
    def pushdown(self, x):
        arr = self.arr
        if arr[x].lazytag:
            arr[2 * x].lazytag = not arr[2 * x].lazytag
            arr[2 * x].sum = arr[2 * x].r - arr[2 * x].l + 1 - arr[2 * x].sum
            arr[2 * x + 1].lazytag = not arr[2 * x + 1].lazytag
            arr[2 * x + 1].sum = arr[2 * x + 1].r - arr[2 * x + 1].l + 1 - arr[2 * x + 1].sum
            arr[x].lazytag = False
    # 区间修改
    def modify(self, id, l, r):
        arr = self.arr
        if arr[id].l >= l and arr[id].r <= r:
            arr[id].sum = (arr[id].r - arr[id].l + 1) - arr[id].sum
            arr[id].lazytag = not arr[id].lazytag
            return
        self.pushdown(id)
        mid = (arr[id].l + arr[id].r) >> 1
        if arr[2 * id].r >= l:
            self.modify(2 * id, l, r)
        if arr[2 * id + 1].l <= r:
            self.modify(2 * id + 1, l, r)
        arr[id].sum = arr[2 * id].sum + arr[2 * id + 1].sum

    # 区间查询
    def query(self, id, l, r):
        arr = self.arr
        if arr[id].l >= l and arr[id].r <= r:
            return arr[id].sum
        if arr[id].r < l or arr[id].l > r:
            return 0
        self.pushdown(id)
        mid = (arr[id].l + arr[id].r) >> 1
        res = 0
        if arr[2 * id].r >= l:
            res += self.query(2 * id, l, r)
        if arr[2 * id + 1].l <= r:
            res += self.query(2 * id + 1, l, r)
        return res

class SegNode:
    def __init__(self):
        self.l = 0
        self.r = 0
        self.sum = 0
        self.lazytag = False


        

到了这里,关于【leetcode难题】2569. 更新数组后处理求和查询【线段树实现01翻转和区间求和模版】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数组对象求和

    使用场景      在一个数组对象中,求对象中某一个字段的总和

    2024年02月07日
    浏览(33)
  • 数组求和的五种方法

    // 数组求和的方法 let arr = [1,2,3,4,5] // 方法一:递归 function sum(arr){ const len = arr.length; if(len === 0) { return 0; } else if(len === 1){ return arr[0]; } else { return arr[0] + sum(arr.slice(1)); } } // 方法二:循环 function sum(arr) { let s = 0; for(let i=0; iarr.length; i++){ s += arr[i] } return s; } // 方法三:map-reduce

    2024年02月10日
    浏览(44)
  • LeetCode2670. 找出不同元素数目差数组:哈希表(预处理)

    力扣题目链接:https://leetcode.cn/problems/find-the-distinct-difference-array/ 给你一个下标从 0 开始的数组 nums ,数组长度为 n 。 nums 的 不同元素数目差 数组可以用一个长度为 n 的数组 diff 表示,其中 diff[i] 等于前缀 nums[0, ..., i] 中不同元素的数目 减去 后缀 nums[i + 1, ..., n - 1] 中不同元

    2024年02月21日
    浏览(42)
  • JS数组求和的几种方法

    这篇文章主要介绍了JS数组求和的几种常用方法 方法一:通过原型对象扩展内置对象方法(即给Array增加方法) 方法二:普通for循环函数求和 方法三:使用递归 方法四:函数式编程reduce 拓展:注意reduce()方法的最后一个参数(下面是个特例),避坑!!! 方法五:forEach遍历

    2024年02月01日
    浏览(47)
  • C语言二维数组中:主次对角线求和,上下三角求和,杨辉三角,矩阵转置

     p8 有些的结论需要直接记住 目录 矩阵转置  主对角线和次对角线 下三角 和上三角(一般是让求和) 下三角  上三角 杨辉三角 不是方阵 需要用到第二个二维数组  b[i][j]=a[i][j] 是方阵     方法1 借助第二个二维数组,同上 方法2    下三角换即可(是方阵的话一般题目都

    2024年01月22日
    浏览(52)
  • 【LeetCode】67. 二进制求和

    难度:简单 给你两个二进制字符串 a 和 b ,以二进制字符串的形式返回它们的和。 示例 1: 示例 2: 提示: 1 = a.length, b.length = 10^4 a 和 b 仅由字符 \\\'0\\\' 或 \\\'1\\\' 组成 字符串如果不是 \\\"0\\\" ,就不含前导零 思路: 从后往前遍历字符逐个判断即可 最后考虑是否进位 sum 1 等价于 sum

    2024年02月05日
    浏览(52)
  • Leetcode67 二进制求和

    给你两个二进制字符串  a  和  b  ,以二进制字符串的形式返回它们的和。      代码  

    2024年02月11日
    浏览(41)
  • Excel·VBA二维数组组合函数、组合求和

    之前的文章《Excel·VBA数组组合函数、组合求和》和《Excel·VBA数组排列函数》,都是针对 一维数组 的组合和排列 二维数组组合:对一个 m行*n列 的二维数组,每行抽取1个元素进行组合,则共有 n ^ m 个组合 代码思路,类似之前的文章“VBA排列函数”尾数循环的方式 举例 组合

    2024年02月11日
    浏览(50)
  • leetcode分类刷题:哈希表(Hash Table)(四、前缀和 处理连续子数组)

    1、leetcode题目里对于 元素加和 的考察可谓是屡见不鲜,包括 简单的限定一个有效答案 的两个或多个元素求和leetcode分类刷题:哈希表(Hash Table)(一、简单的两数之和)、在有序数组内对加和等于target的 三元组、四元组 等的求解leetcode分类刷题:基于数组的双指针(三、

    2024年02月10日
    浏览(38)
  • 代码训练LeetCode(12)二进制求和

    Author: Once Day Date: 2024年3月14日 一位热衷于Linux学习和开发的菜鸟,试图谱写一场冒险之旅,也许终点只是一场白日梦… 漫漫长路,有人对你微笑过嘛… 全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客 参考文章: 67. 二进制求和 - 力扣(LeetCode) 力扣 (LeetCode) 全球极

    2024年03月20日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包