一维：
树状数组 1 ：单点修改，区间查询
题目描述
这是一道模板题。
给定数列a1?,a2?,…,an?，你需要依次进行?q?个操作，操作有两类：
1 i x：给定?i,x，将 ai??加上?x；2 l r：给定?l,r，求?∑i=lr?ai??的值（换言之，求 al?+al+1?+?+ar??的值）。
输入格式
第一行包含?2?个正整数?n,q，表示数列长度和询问个数。保证 1≤n,q≤1e6。
第二行?n?个整数?a1?,a2?,…,an?，表示初始数列。保证?∣ai?∣≤1e6。
接下来?q?行，每行一个操作，为以下两种之一：
1 i x：给定?i,x，将?a[i]?加上?x；2 l r：给定?l,r，求?∑i=lr?ai??的值。
保证?1≤l≤r≤n,?∣x∣≤1e6。
输出格式
对于每个?2 l r?操作输出一行，每行有一个整数，表示所求的结果。
样例
| Input | Output |
|---|
3 2
1 2 3
1 2 0
2 1 3 | 6 |
数据范围与提示
对于所有数据，1≤n,q≤1e6,?∣ai?∣≤1e6,?1≤l≤r≤n,?∣x∣≤1e6。
前缀和思想
AC代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <list>
#include <set>
#include <istream>
#include <sstream>
#include <iomanip>
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
using namespace std;
int n,q;
int a[1000010];
long long tree[1000010];
int lowbit(int x){
return x & -x;
}
void add(int x,int v){
while(x <= n){
tree[x] += v;
x += lowbit(x);
}
}
long long get(int x){
long long cnt = 0;
while(x){
cnt += tree[x];
x -= lowbit(x);
}
return cnt;
}
void solve(){
cin >> n >> q;
for(int i = 1;i <= n;i++){
cin >> a[i];
add(i,a[i]);
}
while(q--){
int id,x,y;
cin >> id >> x >> y;
if(id == 1){
add(x,y);
}
if(id == 2){
cout << get(y) - get(x - 1) << endl;
}
}
return ;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
solve();
return 0;
}
/*
*/
树状数组 2 ：区间修改，单点查询
题目描述
这是一道模板题。
给定数列?a[1],a[2],…,a[n]，你需要依次进行?q?个操作，操作有两类：
1 l r x：给定?l,r,x，对于所有?i∈[l,r]，将?a[i]?加上?x（换言之，将?a[l],a[l+1],…,a[r]?分别加上?x）；2 i：给定?i，求?a[i]?的值。
输入格式
第一行包含?2?个正整数?n,q，表示数列长度和询问个数。保证?1≤n,q≤1e6。
第二行?n?个整数?a[1],a[2],…,a[n]，表示初始数列。保证?|a[i]|\le 10^6∣a[i]∣≤106。
接下来?q?行，每行一个操作，为以下两种之一：
1 l r x：对于所有?i∈[l,r]，将?a[i]?加上?x；2 i：给定?i，求?a[i]?的值。
保证?1≤l≤r≤n,?∣x∣≤1e6。
输出格式
对于每个?2 i?操作，输出一行，每行有一个整数，表示所求的结果。
样例
| Input | Output |
|---|
3 2
1 2 3
1 1 3 0
2 2 | 2 |
数据范围与提示
对于所有数据，1≤n,q≤1e6,?∣a[i]∣≤1e6,?1≤l≤r≤n,?∣x∣≤1e6。
差分+前缀和思想，STL库adjacent_difference动态数组求差分
AC代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <list>
#include <set>
#include <istream>
#include <sstream>
#include <iomanip>
#include <numeric>
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
using namespace std;
int n,q;
int a[1000010],b[1000010];
long long tree[1000010];
int lowbit(int x){
return x & -x;
}
void add(int x,int v){
while(x <= n){
tree[x] += v;
x += lowbit(x);
}
}
long long get(int x){
long long cnt = 0;
while(x){
cnt += tree[x];
x -= lowbit(x);
}
return cnt;
}
void solve(){
cin >> n >> q;
vector<int> c(n + 1);
for(int i = 1;i <= n;i++){
cin >> a[i];
}
adjacent_difference(a + 1,a + 1 + n,c.begin() + 1);
for(int i = 1;i <= n;i++){
tree[i] += c[i];
long long j = i + lowbit(i);
if(j <= n){
tree[j] += tree[i];
}
}
while(q--){
int id,l,r,x;
cin >> id;
if(id == 1){
cin >> l >> r >> x;
add(l,x);
add(r + 1,-x);
}
if(id == 2){
cin >> l;
cout << get(l) << endl;
}
}
return ;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
solve();
return 0;
}
/*
*/
树状数组 3 ：区间修改，区间查询
题目描述
这是一道模板题。
给定数列 a[1],a[2],…,a[n]，你需要依次进行?q?个操作，操作有两类：
1 l r x：给定?l,r,x，对于所有?i∈[l,r]，将?a[i]?加上?x（换言之，将?a[l],a[l+1],…,a[r]?分别加上?x）；2 l r：给定?l,r，求?∑i=lr?a[i]?的值（换言之，求?a[l]+a[l+1]+?+a[r]?的值）。
输入格式
第一行包含?2?个正整数?n,q，表示数列长度和询问个数。保证?1≤n,q≤1e6。
第二行?n?个整数?a[1],a[2],…,a[n]，表示初始数列。保证?∣a[i]∣≤1e6。
接下来?q?行，每行一个操作，为以下两种之一：
1 l r x：对于所有?i∈[l,r]，将?a[i]?加上?x；2 l r：输出?∑i=lr?a[i]?的值。
保证?1≤l≤r≤n,?∣x∣≤1e6。
输出格式
对于每个?2 l r?操作，输出一行，每行有一个整数，表示所求的结果。
样例
| Input | Output |
|---|
5 10
2 6 6 1 1
2 1 4
1 2 5 10
2 1 3
2 2 3
1 2 2 8
1 2 3 7
1 4 4 10
2 1 2
1 4 5 6
2 3 4
| 15
34
32
33
50
|
数据范围与提示
对于所有数据，1≤n,q≤1e6,?∣a[i]∣≤1e6,?1≤l≤r≤n,?∣x∣≤1e6。
差分+前缀和思想，adjacent_difference求差分，记得维护i*b[i]数组时加1ll*防止爆int
AC代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <list>
#include <set>
#include <istream>
#include <sstream>
#include <iomanip>
#include <numeric>
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
using namespace std;
ll n, q;
ll a[1000010];
long long tree1[1000010],tree2[1000010];
ll lowbit(ll x) {
return x & -x;
}
void add(ll p, ll x) {
long long v = p * x;
for (ll i = p; i <= n; i += lowbit(i)) {
tree1[i] += x;
tree2[i] += v;
}
return;
}
long long get(ll x) {
long long ans = 0;
for (ll i = x; i > 0; i -= lowbit(i)) {
ans += (x + 1) * tree1[i] - tree2[i];
}
return ans;
}
void solve() {
cin >> n >> q;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
}
vector<long long> vec(n + 10);
adjacent_difference(a + 1, a + 1 + n, vec.begin() + 1);
for (ll i = 1; i <= n; i++) {
tree1[i] += vec[i];
tree2[i] += 1ll * vec[i] * i;
long long j = i + lowbit(i);
if (j <= n) {
tree1[j] += tree1[i];
tree2[j] += tree2[i];
}
}
while (q--) {
ll flag;
cin >> flag;
if (flag == 1) {
ll l, r, x;
cin >> l >> r >> x;
add(l, x);
add(r + 1, -x);
}
else {
ll l, r;
cin >> l >> r;
cout << get(r) - get(l - 1) << endl;
}
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
/*
*/
二维树状数组：
二维树状数组 1：单点修改，区间查询
题目描述
这是一道模板题。
给出一个?n×m?的零矩阵?A，你需要完成如下操作：
1 x y k：表示元素?Ax,y??自增?k；2 a b c d：表示询问左上角为?(a,b)，右下角为?(c,d)?的子矩阵内所有数的和。
输入格式
输入的第一行有两个正整数?n,m；
接下来若干行，每行一个操作，直到文件结束。
输出格式
对于每个?2?操作，输出一个整数，表示对于这个操作的回答。
样例
| Input | Output |
|---|
2 2
1 1 1 3
1 2 2 4
2 1 1 2 2 | 7 |
数据范围与提示
对于?10%?的数据，n=1；
对于另?10%?的数据，m=1；
对于全部数据，1≤n,m≤2^12,1≤x,a,c≤n,1≤y,b,d≤m,∣k∣≤1e5，保证操作数目不超过?3×1e5，且询问的子矩阵存在。
差分思想
AC代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <list>
#include <set>
#include <istream>
#include <sstream>
#include <iomanip>
#include <numeric>
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
using namespace std;
int n, m;
long long a[5000][5000];
int lowbit(int x) {
return x & -x;
}
void add(int x, int y, int k) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j += lowbit(j)) {
a[i][j] += k;
}
}
return;
}
long long get(int x,int y) {
long long sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
sum += a[i][j];
}
}
return sum;
}
void solve() {
cin >> n >> m;
int flag;
memset(a, 0, sizeof(a));
while (cin >> flag) {
if (flag == 1) {
int x, y, k;
cin >> x >> y >> k;
add(x, y, k);
}
else {
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << get(a - 1,b - 1) + get(c,d) - get(c,b-1)-get(a-1,d) << endl;
}
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
/*
*/
二维树状数组 2：区间修改，单点查询
题目描述
这是一道模板题。
给出一个?n×m?的零矩阵?A，你需要完成如下操作：
1 a b c d k：表示左上角为?(a,b)，右下角为?(c,d)?的子矩阵内所有数都自增?k；2 x y：表示询问元素?Ax,y??的值；
输入格式
输入的第一行有两个正整数?n,m；
接下来若干行，每行一个操作，直到文件结束。
输出格式
对于每个?2?操作，输出一个整数，表示对于这个操作的回答。
样例
| Input | Output |
|---|
2 2
1 1 1 2 2 5
1 1 2 2 2 -3
2 1 1
2 1 2
2 2 1
2 2 2 | 5
2
5
2 |
数据范围与提示
1≤n,m≤2^12,1≤x,a,c≤n,1≤y,b,d≤m,∣k∣≤1e5，保证操作数目不超过?3×1e5，且操作的子矩阵存在。
差分思想
AC代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <list>
#include <set>
#include <istream>
#include <sstream>
#include <iomanip>
#include <numeric>
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
using namespace std;
int n, m;
long long a[5000][5000];
int lowbit(int x) {
return x & -x;
}
void add(int x, int y, int k) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j += lowbit(j)) {
a[i][j] += k;
}
}
return;
}
long long get(int x, int y) {
long long sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
sum += a[i][j];
}
}
return sum;
}
void solve() {
cin >> n >> m;
int flag;
while (cin >> flag) {
if (flag == 1) {
int a, b, c, d, k;
cin >> a >> b >> c >> d >> k;
add(a, b, k);
add(a, d + 1, -k);
add(c + 1, b, -k);
add(c + 1, d + 1, k);
}
else {
int x, y;
cin >> x >> y;
cout << get(x, y) << endl;
}
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
/*
*/
二维树状数组 3：区间修改，区间查询
题目描述
这是一道模板题。
给定一个大小为?N×M?的零矩阵，直到输入文件结束，你需要进行若干个操作，操作有两类：
-
1 a b c d x，表示将左上角为?(a,b)，右下角为?(c,d)?的子矩阵全部加上?x；
-
2 a b c d，表示询问左上角为?(a,b)，右下角为?(c,d)?为顶点的子矩阵的所有数字之和。
输入格式
第一行两个正整数 ，其中?n,m?分别表示矩阵的行数与列数。
接下来若干行直到文件结束，均代表你需要进行的操作。
输出格式
对于每个?2?操作，输出一行代表查询的结果。
样例
| Input | Output |
|---|
4 4
1 1 1 3 3 2
1 2 2 4 4 1
2 2 2 3 3 | 12 |
数据范围与提示
对于10%?的数据，1≤n,m≤16，操作不超过?200?个；
对于60%?的数据，1≤n,m≤512；
对于?100%?的数据，1≤n,m≤2048,∣x∣≤500，操作不超过?2×1e5?个，保证运算过程中及最终结果均不超过?64?位带符号整数类型的表示范围，并且修改与查询的子矩阵存在。
差分思想
AC代码：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <list>
#include <set>
#include <istream>
#include <sstream>
#include <iomanip>
#include <numeric>
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
using namespace std;
int n, m;
long long tree1[2050][2050], tree2[2050][2050], tree3[2050][2050], tree4[2050][2050];
int lowbit(int x) {
return x & -x;
}
void add(int x, int y, int k) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= m; j += lowbit(j)) {
tree1[i][j] += k;
tree2[i][j] += k * x;
tree3[i][j] += k * y;
tree4[i][j] += k * x * y;
}
}
return;
}
long long get(int x, int y) {
long long sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
sum += (x + 1) * (y + 1) * tree1[i][j] - (x + 1) * tree3[i][j] - (y + 1) * tree2[i][j] + tree4[i][j];
}
}
return sum;
}
void solve() {
cin >> n >> m;
int flag;
while (cin >> flag) {
if (flag == 1) {
int a, b, c, d, x;
cin >> a >> b >> c >> d >> x;
add(a, b, x);
add(a, d + 1, -x);
add(c + 1, b, -x);
add(c + 1, d + 1, x);
}
else {
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << get(a - 1, b - 1) + get(c, d) - get(c, b - 1) - get(a - 1, d) << endl;
}
}
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
/*
*/