range-sum-query-immutable

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an integer array <code>nums</code>, handle multiple queries of the following type:

<ol>
	<li>Calculate the sum of the elements of <code>nums</code> between indices <code>left</code> and <code>right</code> inclusive where <code>left &lt;= right</code>.</li>
</ol>

Implement the <code>NumArray</code> class:

<ul>
	<li><code>NumArray(int[] nums)</code> Initializes the object with the integer array <code>nums</code>.</li>
	<li><code>int sumRange(int left, int right)</code> Returns the sum of the elements of <code>nums</code> between indices <code>left</code> and <code>right</code> inclusive (i.e. <code>nums[left] + nums[left + 1] + ... + nums[right]</code>).</li>
</ul>

&nbsp;
Example 1:

<pre>
Input
[&quot;NumArray&quot;, &quot;sumRange&quot;, &quot;sumRange&quot;, &quot;sumRange&quot;]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

Explanation
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 104</code></li>
	<li><code>-105 &lt;= nums[i] &lt;= 105</code></li>
	<li><code>0 &lt;= left &lt;= right &lt; nums.length</code></li>
	<li>At most <code>104</code> calls will be made to <code>sumRange</code>.</li>
</ul>

Range Sum Query - Immutable

Range Sum Query 2D - Immutable

range-sum-query-2d-immutable

二维区域和检索 - 矩阵不可变

Range Sum Query - Mutable

range-sum-query-mutable

区域和检索 - 数组可修改

Maximum Size Subarray Sum Equals k

maximum-size-subarray-sum-equals-k

和等于 k 的最长子数组长度

Sum of Variable Length Subarrays

sum-of-variable-length-subarrays

变长子数组求和

Design

Array

Prefix Sum

给定一个整数数组 &nbsp;<code>nums</code>，处理以下类型的多个查询:

<ol>
	<li>计算索引&nbsp;<code>left</code>&nbsp;和&nbsp;<code>right</code>&nbsp;（包含 <code>left</code> 和 <code>right</code>）之间的 <code>nums</code> 元素的 和 ，其中&nbsp;<code>left &lt;= right</code></li>
</ol>

实现 <code>NumArray</code> 类：

<ul>
	<li><code>NumArray(int[] nums)</code> 使用数组 <code>nums</code> 初始化对象</li>
	<li><code>int sumRange(int i, int j)</code> 返回数组 <code>nums</code>&nbsp;中索引&nbsp;<code>left</code>&nbsp;和&nbsp;<code>right</code>&nbsp;之间的元素的 总和 ，包含&nbsp;<code>left</code>&nbsp;和&nbsp;<code>right</code>&nbsp;两点（也就是&nbsp;<code>nums[left] + nums[left + 1] + ... + nums[right]</code>&nbsp;)</li>
</ul>

&nbsp;

示例 1：

<pre>
输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 104</code></li>
	<li><code>-105&nbsp;&lt;= nums[i] &lt;=&nbsp;105</code></li>
	<li><code>0 &lt;= i &lt;= j &lt; nums.length</code></li>
	<li>最多调用 <code>104</code> 次 <code>sumRange</code> 方法</li>
</ul>