题目描述
给定一个长度为 N 的数列 A,以及 M 条指令,每条指令可能是以下两种之一:
C l r d,表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r,表示询问数列中第 l∼r 个数的和。
对于每个询问,输出一个整数表示答案。
输入格式
第一行两个整数 N,M。
第二行 N 个整数 A[i]。
接下来 M 行表示 M 条指令,每条指令的格式如题目描述所示。
输出格式
对于每个询问,输出一个整数表示答案。
每个答案占一行。
数据范围
1≤N,M≤105,
|d|≤10000,
|A[i]|≤109
样例
输入样例:
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
输出样例:
4
55
9
15
算法1
(差分数组(BT实现)) $O()$
时间复杂度
参考文献
python3 代码
class BitTree:
def __init__(self, n: int):
self.n = n
self.tree = [0 for _ in range(n + 1)]
self.tree_i = [0 for _ in range(n + 1)]
def lowbit(self, x: int) -> int:
return x & (-x)
def add(self, idx: int, val: int) -> None:
i = idx
while i <= self.n:
self.tree[i] += val
self.tree_i[i] += idx * val
i += self.lowbit(i)
def query(self, idx: int) -> int:
res = 0
i = idx
while 1 <= i:
res += (idx + 1) * self.tree[i] - self.tree_i[i]
i -= self.lowbit(i)
return res
def main():
n, m = map(int, input().split())
A = [0] + list(map(int, input().split()))
presum = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
presum[i] = presum[i - 1] + A[i]
#--------- 差分数组(BT实现)
BT = BitTree(n)
for _ in range(m):
line = input().split()
if line[0] == 'C':
l, r, val = int(line[1]), int(line[2]), int(line[3])
BT.add(l, val)
if r + 1 <= n:
BT.add(r + 1, -val)
else:
l, r = int(line[1]), int(line[2])
cur = presum[r] - presum[l - 1] + BT.query(r) - BT.query(l - 1)
print(cur)
if __name__ == "__main__":
main()
C++ 代码
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
class BitTree
{
public:
int n;
long long * tree;
long long * tree_i;
BitTree() {}
BitTree(int n_)
{
n = n_;
tree = new long long[n + 1];
tree_i = new long long[n + 1];
for (int i = 0; i < n + 1; i ++)
{
tree[i] = 0;
tree_i[i] = 0LL;
}
}
int lowbit(int x)
{
return x & (-x);
}
void add(int idx, int val)
{
int i = idx;
while (i <= n)
{
tree[i] += val;
tree_i[i] += idx * val;
i += lowbit(i);
}
}
long long query(int idx)
{
long long res = 0LL;
int i = idx;
while (1 <= i)
{
res += (idx + 1) * tree[i] - tree_i[i];
i -= lowbit(i);
}
return res;
}
};
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n; cin >> n;
int m; cin >> m;
int A[n + 1];
for (int i = 1; i < n + 1; i ++)
{
cin >> A[i];
}
long long presum[n + 1];
presum[0] = 0LL;
for (int i = 1; i < n + 1; i ++)
{
presum[i] = presum[i - 1] + A[i];
}
//-------- 差分数组(BT实现)
BitTree BT = BitTree(n);
for (int i = 0; i < m; i ++)
{
char op; cin >> op;
if (op == 'C')
{
int l; cin >> l;
int r; cin >> r;
int val; cin >> val;
BT.add(l, val);
if (r + 1 <= n)
{
BT.add(r + 1, -val);
}
}
else
{
int l; cin >> l;
int r; cin >> r;
long long cur = presum[r] - presum[l - 1] + BT.query(r) - BT.query(l - 1);
cout << cur << endl;
}
}
return 0;
}
java 代码
import java.util.Scanner;
class BitTree
{
int n;
long [] tree; // (idx + 1) * sum(b[i])
long [] tree_i; // i * b[i]
BitTree() {}
BitTree(int n_)
{
n = n_;
tree = new long [n + 1];
tree_i = new long[n + 1];
}
int lowbit(int x)
{
return x & (-x);
}
void add(int idx, int val)
{
int i = idx;
while (i <= n)
{
tree[i] += val;
tree_i[i] += idx * val;
i += lowbit(i);
}
}
long query(int idx)
{
long res = 0L;
int i = idx;
while (1 <= i)
{
res += (idx + 1) * tree[i] - tree_i[i];
i -= lowbit(i);
}
return res;
}
}
public class Main
{
public static void main(String [] args)
{
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int [] A = new int[n + 1];
for (int i = 1; i < n + 1; i ++)
{
A[i] = scan.nextInt();
}
long [] presum = new long [n + 1];
for (int i = 1; i < n + 1; i ++)
{
presum[i] = presum[i - 1] + A[i];
}
//-------- 差分数组(BT实现)
BitTree BT = new BitTree(n);
for (int i = 0; i < m; i ++)
{
char op = scan.next().charAt(0);
if (op == 'C')
{
int l = scan.nextInt();
int r = scan.nextInt();
int val = scan.nextInt();
BT.add(l, val);
if (r + 1 <= n)
{
BT.add(r + 1, -val);
}
}
else
{
int l = scan.nextInt();
int r = scan.nextInt();
long cur = presum[r] - presum[l - 1] + BT.query(r) - BT.query(l - 1);
System.out.println(cur);
}
}
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla