文档章节

303. Range Sum Query - Immutable

N3verL4nd
 N3verL4nd
发布于 2017/03/25 10:20
字数 228
阅读 1
收藏 0

Given an integer arraynums, find the sum of the elements between indicesiandj(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.

  1. There are many calls tosumRangefunction.
维护一个数组,然后局部求和,典型的树状数组,或者使用线段树。
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
using namespace std;

class NumArray {
public:
	NumArray(vector<int> &nums) 
	{
		n = nums.size();
		for (int i = 1; i <= n; i++)
		{
			num[i] = 0;
		}
		for (vector<int>::size_type i = 0; i < nums.size(); i++)
		{
			Update(i + 1, nums[i]);
		}
	}

	int sumRange(int i, int j) 
	{
		return Sum(j + 1) - Sum(i);
	}
private:
	int LowBit(int x)
	{
		return x & (-x);
	}
	int Sum(int end)
	{
		int sum = 0;
		while (end > 0)
		{
			sum += num[end];
			end -= LowBit(end);
		}
		return sum;
	}
	void Update(int pos, int value)
	{
		while (pos <= n)
		{
			num[pos] += value;
			pos += LowBit(pos);
		}
	}
	int num[1000000];
	int n;
};


int main()
{
	vector<int>vec{ -2, 0, 3, -5, 2, -1 };
	NumArray ss(vec);
	cout << ss.sumRange(0, 5);
	return 0;
}

num数组开的比较大

树状数组学习笔记:

© 著作权归作者所有

N3verL4nd
粉丝 1
博文 379
码字总数 481243
作品 0
朝阳
私信 提问
LeetCode:Range Sum Query 2D -Immutable-矩阵指定区域内的元素和

1、题目名称 Range Sum Query 2D(矩阵指定区域内的元素和) 2、题目地址 https://leetcode.com/problemset/algorithms/ 3、题目内容 英文:Given a 2D matrix matrix, find the sum of the...

北风其凉
2015/11/15
1K
0
Leetcode 303. Range Sum Query - Immutable

版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn.net/Quincuntial/article/details/87634113 文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Descr...

SnailTyan
02/18
0
0
[LeetCode] Range Sum Query 2D - Mutable 二维区域和检索 - 可变

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). The above rectangl......

机器的心脏
2017/12/15
0
0
[LeetCode] Count of Range Sum 区间和计数

Given an integer array , return the number of range sums that lie in inclusive. Range sum is defined as the sum of the elements in between indices and ( ≤ ), inclusive. Note: ......

机器的心脏
2017/12/15
0
0
LeetCode:Range Sum Query - Immutable - 数组指定区间内的元素和

1、题目名称 Range Sum Query(数组指定区间内的元素和) 2、题目地址 https://leetcode.com/problems/range-sum-query-immutable/ 3、题目内容 英文:Given an integer array nums, find t...

北风其凉
2015/11/10
3.3K
0

没有更多内容

加载失败,请刷新页面

加载更多

PostgreSQL参数search_path影响及作用

search_path稍微熟悉PG就会用到,用法这里就不必讲,本篇主要讲它在程序里怎样处理。 1、GUC参数定义 这是个 config_string 参数 {{"search_path", PGC_USERSET, CLIENT_CONN_STATEMENT,...

有理想的猪
58分钟前
8
0
Qt程序各个平台打包发布及安装程序大全

本文链接:https://blog.csdn.net/zhengtianzuo06/article/details/78468111 通用: 1.准备图标 图标可以直接使用一般格式的图片制作, 比如jpg, png等 推荐使用Photoshop制作原始图 推荐使用I...

shzwork
今天
4
0
springboot2.0 maven打包分离lib,resources

springboot将工程打包成jar包后,会出现获取classpath下的文件出现测试环境正常而生产环境文件找不到的问题,这是因为 1、在调试过程中,文件是真实存在于磁盘的某个目录。此时通过获取文件路...

陈俊凯
今天
22
0
BootStrap

一、BootStrap 简洁、直观、强悍的前端开发框架,让web开发更加迅速、简单 中文镜像网站:http://www.bootcss.com 用于开发响应式布局、移动设备优先的WEB项目 1、使用boot 创建文件夹,在文...

wytao1995
今天
10
0
小知识:讲述Linux命令别名与资源文件的区别

别名 别名是命令的快捷方式。为那些需要经常执行,但需要很长时间输入的长命令创建快捷方式很有用。语法是: alias ppp='ping www.baidu.com' 它们并不总是用来缩短长命令。重要的是,你将它...

老孟的Linux私房菜
今天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部