leetcode Range Sum Query – Immutable

leetcode Range Sum Query – Immutable

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

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1

sumRange(2, 5) -> -1

sumRange(0, 5) -> -3

Note:

  1. You may assume that the array does not change.
  2. There are many calls to sumRange function.

题目地址  leetcode Range Sum Query – Immutable

题意:

给你一个数组,让你求i,j的和

  • 数组不变
  • 有许多次的计算

思路:

直接记录和。。。。

 

 

复习一下fenwick树,支持修改。(本题数组不变)当然也可以线段树。

关于fenwick tree看这里:  Fenwick tree (binary indexed tree) 

 

更进一步:

leetcode Range Sum Query – Mutable

 

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Range Sum Query – Immutable
本文地址:https://www.hrwhisper.me/leetcode-range-sum-query-immutable/

听说长得好看的已经打赏了

Leetcode , , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *