3月18号

哈希表:

概念:在哈希表中存有很多的keys(关键字),每个keys都对应一个values,也就是对应一个值.

引入数组与链表:

        数组:寻找地址容易,插入和删除元素困难.

        链表:寻找地址困难,插入和删除元素困难.

哈希表就把数组与链表结合起来了,左边是数组,每个数组又指向一个链表的数据结构.

哈希函数:

哈希函数能快速的将一个数值转换为哈希值(整数),所以哈希表必须保持哈希值计算的一致,如果两个哈希值是不相同的,那么这两个哈希值的原始输入也是不相同的.

那如果两个不同的输入得到相同的哈希值==哈希值冲突.

我们输入关键字X,使用哈希函数f(x)来计算出哈希值y,然后用哈希值y来找特定的数组下标,并在对应位置插入新数据.

X=>f(X)=y=>y%Array.length=>Array Position of X

哈希表支持的操作:

add(key,value);  将一对新的键值对加入哈希表

get(K);                 通过特定的关键字拿到其所对应的数值

remove(key);      通过关键字,删除哈希表对应的键值对

getSize();            当前键值对的数量

isEmpty();           查看哈希表是否为空

题目描述

给定 n 个正整数组成的数列 a1​,a2​,⋯,an​ 和 m 个区间 [li​,ri​]，分别求这 m 个区间的区间和。

对于所有测试数据，n,m≤105,ai​≤104

输入格式

第一行，为一个正整数 n 。

第二行，为 n 个正整数 a1​,a2​,⋯,an​

第三行，为一个正整数 m 。

接下来 m 行，每行为两个正整数 li​,ri​ ，满足1≤li​≤ri​≤n

输出格式

共 m 行。

第 i 行为第 i 组答案的询问。

输入输出样例

输入 #1复制

4
4 3 2 1
2
1 4
2 3

输出 #1复制

10
5

说明/提示

样例解释：第 1 到第 4 个数加起来和为 10。第 2 个数到第 3 个数加起来和为 5。

对于 50% 的数据：n,m≤1000；

对于 100% 的数据：1≤n,m≤105，1≤ai​≤104

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,a[100005],b[100005];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i]+b[i-1];
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		int s=b[y]-b[x-1];
		cout<<s<<endl;
	}
	return 0;
}