树状数组
1.单点修改，区间查询
[(https://www.luogu.com.cn/problem/P3374)]
题目描述
如题，已知一个数列，你需要进行下面两种操作：
将某一个数加上 x 求出某区间每一个数的和
输入格式
第一行包含两个正整数 n,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 n 个用空格分隔的整数，其中第 i个数字表示数列第 i 项的初始值。
接下来 m 行每行包含 3 个整数，表示一个操作，具体如下：
1 x k 含义：将第 x 个数加上 k
2 x y 含义：输出区间 [x,y] 内每个数的和
输出格式
输出包含若干行整数，即为所有操作2的结果。
输入输出样例
输入
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
输出
14
16
#include <bits/stdc++.h>
#define N (500000 + 10) /*------------------ #define ------------------*/
#define M (400000 + 10)
#define MOD (1000000000 + 7)
//#define MOD (998244353)
#define INF (0x3f3f3f3f)
#define LNF (3e18)
#define mod(a,b) (((a)%(b)+(b))%(b))
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define fi first
#define se second
#define vvi vector<vector<int>>
#define vi vector<int>
#define vvl vector<vector<LL>>
#define vl vector<LL>
#define _vvi(n,m,k) vector<vector<int>>(n,vector<int>(m,k))
#define _vi(n,k) vector<int>(n,k)
#define _vvl(n,m,k) vector<vector<LL>>(n,vector<LL>(m,k))
#define _vl(n,k) vector<LL>(n,k)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<int,LL> PIL;
typedef pair<LL,int> PLI;
typedef pair<double,double> PDD;
int n,Q;
int b[N];
/*
让A[p] += k
add(p,k);
假如说，让A[p] = k
add(p,-sum(p,p));
add(p,k);
*/
void add(int p,int k){
for(int i = p;i <= n;i += i & -i)
b[i] += k;
}
LL sum(int p){
LL ret = 0;
for(int i = p;i;i -= i & -i)
ret += b[i];
return ret;
}
LL sum(int l,int r){
return sum(r) - sum(l - 1);
}
auto solve(){
cin >> n >> Q;
for(int i = 1;i <= n;i ++ ){
int x; cin >> x;
add(i,x);
}
while(Q -- ){
int op,x,y;
cin >> op >> x >> y;
if(op == 1){
add(x,y);
}else{
cout << sum(x,y) << '\n';
}
}
}
signed main(){
IOS
int T = 1;
//cin >> T;
while(T -- ) solve();
//while(T -- ) cout << (solve() ? "YES" : "NO") << '\n';
return 0;
}
2.区间修改，单点查询
242.一个简单的整数问题
[(https://www.acwing.com/problem/content/248/)]
题目描述
给定长度为 N 的数列 A，然后输入 M 行操作指令。
第一类指令形如 C l r d，表示把数列中第 l∼r 个数都加 d。
第二类指令形如 Q x，表示询问数列中第 x 个数的值。
对于每个询问，输出一个整数表示答案。
输入格式
第一行包含两个整数 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
Q 1
Q 2
C 1 6 3
Q 2
输出样例：
4
1
2
5
#include <bits/stdc++.h>
#define N (200000 + 10) /*------------------ #define ------------------*/
#define M (400000 + 10)
#define MOD (1000000000 + 7)
//#define MOD (998244353)
#define INF (0x3f3f3f3f)
#define LNF (3e18)
#define mod(a,b) (((a)%(b)+(b))%(b))
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define fi first
#define se second
#define vvi vector<vector<int>>
#define vi vector<int>
#define vvl vector<vector<LL>>
#define vl vector<LL>
#define _vvi(n,m,k) vector<vector<int>>(n,vector<int>(m,k))
#define _vi(n,k) vector<int>(n,k)
#define _vvl(n,m,k) vector<vector<LL>>(n,vector<LL>(m,k))
#define _vl(n,k) vector<LL>(n,k)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<int,LL> PIL;
typedef pair<LL,int> PLI;
typedef pair<double,double> PDD;
int n,Q;
int a[N],b[N];
int tr[N];
/*
单点修改，区间查询<=>区间修改，单点查询，可以相互转换
[l,r]+d ======== b[l]+d,b[r+1]-d
x ======== sum(1,x)
*/
void add(int x,int k){
for(int i = x;i <= n;i += i & -i)//lowbit(x)==> x & x
tr[i] += k;
}
LL sum(int x)//修改x后，更新其他节点
{
LL ret = 0;
for(int i = x;i;i -= i & -i)
ret += tr[i];
return ret;
};
void add(int l,int r,int d){
add(l,d),add(r + 1,-d);
}
LL sum(int l,int r){
return sum(r) - sum(l - 1);
}
auto solve(){
cin >> n >> Q;
for(int i = 1;i <= n;i ++ ) cin >> a[i];
for(int i = 1;i <= n;i ++ ) b[i] = a[i] - a[i - 1];
for(int i = 1;i <= n;i ++ )
add(i,b[i]);
while(Q -- ){
char op;
cin >> op;
if(op == 'C'){
int l,r,d;
cin >> l >> r >> d;
add(l,r,d);
}else{
int x;
cin >> x;
cout << sum(x) << '\n';
}
}
}
signed main(){
IOS
int T = 1;
//cin >> T;
while(T -- ) solve();
//while(T -- ) cout << (solve() ? "YES" : "NO") << '\n';
return 0;
}
3.区间修改，区间查询
243. 一个简单的整数问题2
[(https://www.acwing.com/problem/content/244/)]
题目描述
给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
1.C l r d，表示把 A[l],A[l+1],…,A[r] 都加上d。
2.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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int a[N];
LL tr1[N]; // 维护b[i]的前缀和
LL tr2[N]; // 维护b[i] * i的前缀和
int lowbit(int x)
{
return x & -x;
}
void add(LL tr[], int x, LL c)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
LL sum(LL tr[], int x)
{
LL res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
LL prefix_sum(int x)
{
return sum(tr1, x) * (x + 1) - sum(tr2, x);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ )
{
int b = a[i] - a[i - 1];
add(tr1, i, b);
add(tr2, i, (LL)b * i);
}
while (m -- )
{
char op[2];
int l, r, d;
scanf("%s%d%d", op, &l, &r);
if (*op == 'Q')
{
printf("%lld\n", prefix_sum(r) - prefix_sum(l - 1));
}
else
{
scanf("%d", &d);
// a[l] += d
add(tr1, l, d), add(tr2, l, l * d);
// a[r + 1] -= d
add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
}
}
return 0;
}
