题目描述
输入一个长度为 \(n\) 的整数序列。
接下来再输入 \(m\) 个询问，每个询问输入一对 \(l, r\)。
对于每个询问，输出原序列中从第 \(l\) 个数到第 \(r\) 个数的和。
输入格式
第一行包含两个整数 \(n\) 和 \(m\)。
第二行包含 \(n\) 个整数，表示整数数列。
接下来 \(m\) 行，每行包含两个整数 \(l\) 和 \(r\)，表示一个询问的区间范围。
输出格式
共 \(m\) 行，每行输出一个询问的结果。
数据范围
\(1 \le l \le r \le n,\)
\(1 \le n,m \le 100000,\)
\(-1000 \le 数列中元素的值 \le 1000\)
输入样例：
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例：
3
6
10
算法
区间和这里提供三种做法：前缀和，线段树，树状数组
前缀和
思路与推导
所谓前缀和，就是我们开一个\(s[]\)数组来维护\(a[]\)数组的前缀和
其中\(s_{x} = \sum_{i = 1}^{x} a_{i}\)
如果我们要查询\(\sum_{i = l}^{r} a_{i}\)的话
因为\(\sum_{i=l}^{r} a_{i} + \sum_{i=1}^{l-1} a_{i} = \sum_{i = 1}^{r} a_{i}\)
所以\(\sum_{i=l}^{r} a_{i} = \sum_{i = 1}^{r} a_{i} - \sum_{i=1}^{l-1} a_{i}\)
我们已经定义了\(s_{x} = \sum_{i = 1}^{x} a_{i}\)
将\(s_x\)带入上面的算式可以得到
\(\sum_{i=l}^{r} a_{i} = s_{r} - s_{l-1}\)
我们这道题目只需用\(O(n)\)时间预处理
怎么预处理呢
\(s_{x} = \sum_{i = 1}^{x} a_{i}, s_{x + 1} = \sum_{i = 1}^{x + 1} a_{i} = \sum_{i=1}^{x} a_{i} + a_{x+1}\)
所以我们只要确定了\(s_{1} = a_{1}\)
后面的部分循环即可
时间复杂度
\(预处理O(n), 查询O(1)\)
代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], m, s[N];
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;i ++ )
scanf("%d", &a[i]);
//预处理s数组
s[1] = a[1];
for (int i = 2; i <= n; i ++ )
s[i] = s[i - 1] + a[i];
int l, r;
while (m -- )
{
scanf("%d%d", &l, &r);
printf("%d\n",s[r] - s[l - 1]);
}
return 0;
}
线段树
思路
这里就不具体说线段树了，这里要维护的区间问题是区间和，不需要修改，故线段树也很合适，开的结构体里面放\({l, r, sum}\)即可
时间复杂度
\(建树O(nlogn),查询O(logn)\)
代码
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n, m, a[N];
struct Seg
{
int l, r, sum;
} tr[N << 2]; //线段树要开四倍空间
void build(int p, int l, int r) //代表编号为p的节点管理[l, r]这个区间
{
Seg& cur = tr[p];
cur.l = l, cur.r = r;
if (l == r) return void(cur.sum = a[l]); //叶子节点直接赋值
int mid = cur.l + cur.r >> 1; //取中间点
build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r); //左右建子树
cur.sum = tr[p << 1].sum + tr[p << 1 | 1].sum; // pushup操作
}
int query(int p, int l, int r)
{
Seg& cur = tr[p];
if (cur.l >= l && cur.r <= r) return cur.sum; // 完全包含直接返回
int mid = cur.l + cur.r >> 1, s = 0;
if (l <= mid) s += query(p << 1, l, r); //左子包含递归左子
if (r > mid) s += query(p << 1 | 1, l, r); // 右字包含递归右子
return s;
}
int main()
{
scanf("%d%d", &n, &m);
//读入并建树
for (int i = 1; i <= n; i ++ )
scanf("%d", &a[i]);
build(1, 1, n);
while (m -- )
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", query(1, l, r));
}
return 0;
}
树状数组
思路
树状数组本来就可以维护前缀
所以这里用树状数组
这里提供两种写法，一种是普通BIT，一种是面向对象泛型BIT
时间复杂度
\(建树O(nlogn),查询O(logn)\)
比线段树快
代码
普通写法
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int tr[N], n, Q, a[N];
void add(int x, int v)
{
for (; x <= n; x += x & -x) tr[x] += v;
}
int query(int x)
{
int res = 0;
for (; x; x -= x & -x) res += tr[x];
return res;
}
int main()
{
scanf("%d%d", &n, &Q);
for (int i = 1; i <= n; i ++ )
scanf("%d", &a[i]), add(i, a[i]);
while (Q -- )
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", query(r) - query(l - 1));
}
return 0;
}
面向对象
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, Q, a[N];
template<typename T>
struct Bit
{
T c[N];
void add(T x, const T v)
{
for (; x <= n; x += x & -x) c[x] += v;
}
T query(T x)
{
T res = 0;
for (; x; x -= x & -x) res += c[x];
return res;
}
} ; Bit<int> tr;
int main()
{
scanf("%d%d", &n, &Q);
for (int i = 1; i <= n; i ++ )
scanf("%d", &a[i]), tr.add(i, a[i]);
while (Q -- )
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", tr.query(r) - tr.query(l - 1));
}
return 0;
}
时间对比
\(前缀和100ms,线段树401ms,树状数组(1) 202ms, 树状数组(2) 223ms\)
撇去评测机的微小影响
速度排名是：前缀和，树状数组（1），树状数组（2），线段树
End
写线段树和BIT有一点大炮打蚊子的感觉，但也不失为一次练习
标签：795,前缀,树状,int,sum,数组,线段 From： https://www.cnblogs.com/StkOvflow/p/16994545.html