Range Sum Query - Mutable

2024-08-23 20:32
文章标签 range sum query mutable

本文主要是介绍Range Sum Query - Mutable,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

先补知识:

Segment Tree 线段树

Binary Indexed Tree   树状数组


明天再补充









Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The  update(i, val)  function modifies  nums  by updating the element at index  i  to  val .

Example:

Given nums = [1, 3, 5]sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

题意很好理解。返回部分和  可以修改某个数同时返回的部分和会更新

代码参照 YRB 总结的很好,而且是用java写的,一个题会用好几种方法做 赞 最近好多都是看它的博客

http://www.cnblogs.com/yrbbest/p/5056739.html


public class NumArray {private class SegmentTreeNode{public int start;public int end;public int sum;public SegmentTreeNode left,right;public SegmentTreeNode(int start,int end){this.start=start;this.end=end;this.sum=0;}}private SegmentTreeNode root;public NumArray(int[] nums) {this.root=buildTree(nums,0,nums.length-1);}public void update(int i, int val) {update(root,i,val);}public void update(SegmentTreeNode node,int position, int val){if(node.start==position&&node.end==position){node.sum=val;return ;}int mid=node.start+(node.end-node.start)/2;if(position<=mid){update(node.left,position,val);}else{update(node.right,position,val);}node.sum=node.left.sum+node.right.sum;}public int sumRange(int i, int j) {return sumRange(root,i,j);}private int sumRange(SegmentTreeNode node,int lo,int hi){if(node.start==lo&&node.end==hi)return node.sum;int mid=node.start+(node.end-node.start)/2;if(hi<=mid){return sumRange(node.left,lo,hi);}else if(lo>mid){return sumRange(node.right,lo,hi);}else {return sumRange(node.left,lo,mid)+sumRange(node.right,mid+1,hi);}}private SegmentTreeNode buildTree(int []nums,int lo,int hi){if(lo>hi){return null;}            else{SegmentTreeNode node=new SegmentTreeNode(lo,hi);if(lo==hi){node.sum=nums[lo];}else{int mid=lo+(hi-lo)/2;node.left=buildTree(nums,lo,mid);node.right=buildTree(nums,mid+1,hi);node.sum=node.left.sum+node.right.sum;}return node;}}
}


这篇关于Range Sum Query - Mutable的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1100426

相关文章

SpringBoot基于MyBatis-Plus实现Lambda Query查询的示例代码

《SpringBoot基于MyBatis-Plus实现LambdaQuery查询的示例代码》MyBatis-Plus是MyBatis的增强工具,简化了数据库操作,并提高了开发效率,它提供了多种查询方... 目录引言基础环境配置依赖配置(Maven)application.yml 配置表结构设计demo_st

最大流=最小割=最小点权覆盖集=sum-最大点权独立集

二分图最小点覆盖和最大独立集都可以转化为最大匹配求解。 在这个基础上,把每个点赋予一个非负的权值,这两个问题就转化为:二分图最小点权覆盖和二分图最大点权独立集。   二分图最小点权覆盖     从x或者y集合中选取一些点,使这些点覆盖所有的边,并且选出来的点的权值尽可能小。 建模:     原二分图中的边(u,v)替换为容量为INF的有向边(u,v),设立源点s和汇点t

如何导入sun.misc.BASE64Encoder和sum.misc.BASE64Decoder

右击项目名--->Build Path--->Configure Build Path...--->java Build Path--->Access rules:1 rule defined,added to all librar...   --->Edit --->Add...

C++中的mutable关键字详解

目录 1.概述 2.使用场景 3.示例 4.mutable修饰Lambda表达式 5.注意事项 1.概述         在C++中,mutable也是为了突破const的限制而设置的。被mutable修饰的变量,将永远处于可变的状态,即使在一个const函数中。         我们知道,被const关键字修饰的函数的一个重要作用就是为了能够保护类中的成员变量。即:该函数可以

18. 4 Sum

题目: 解答: 与之前的三数之和的解法类似,也是先排序,然后不断剔除不可能的条件,最后两个参数,通过两头求和计算得出。 代码: class Solution {public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> result;int len = nums.size

构建现代API:FastAPI中Query与Body参数的最佳搭配

在FastAPI中,Query 和 Body 是两种不同的依赖注入器,它们的应用场景取决于你的具体需求。以下是它们各自常见的使用场景: Query 参数 使用场景: 当你需要从URL中获取一些简单的参数时,例如过滤、排序、分页等。 当数据量不大,且可以作为URL的一部分安全传输时。当数据不需要复杂的结构时。 Body 参数 使用场景: 当你需要发送较为复杂的数据结构时,例如包含多个字段

apt-get update更新源时,出现“Hash Sum mismatch”问题

转载自:apt-get update更新源时,出现“Hash Sum mismatch”问题 当使用apt-get update更新源时,出现下面“Hash Sum mismatch”的报错,具体如下: root@localhost:~# apt-get update ...... ...... W: Failed to fetch http://us.archive.ubuntu.com/ub

MySql 1264 - Out of range value for column 异常

前段时间操作数据库,本是一个很简单的修改语句,却报了  1264 - Out of range value for column字段类型官网  当时一看懵逼了,网上很多都说是配置的问题,需要修改my.ini文件,这个方式我没有试过,我想肯定还有其它方法,经过慢慢排 查发现表里的字段为 decimal(10,3) ,这说明小数点前只有7位,保留了3位小数点,而值在小数点前却有8位,这就导致了错误

【硬刚ES】ES基础(二十) 单字符串多字段查询:Dis Max Query

本文是对《【硬刚大数据之学习路线篇】从零到大数据专家的学习指南(全面升级版)》的ES部分补充。

【硬刚ES】ES基础(十九) Query Filtering 与多字符串多字段查询

本文是对《【硬刚大数据之学习路线篇】从零到大数据专家的学习指南(全面升级版)》的ES部分补充。