1. 树状数组操作
题目描述
给你n个数，创建一个树状数组，并执行相应操作，按格式要求输出操作结果。执行的操作有以下两种形式：
C i dt ，表示更新A[i]，使得A[i]=A[i]+dt，其中1<=i<=n；
Q i j ，表示询问区间和，即A[i]+A[i+1]+…+A[j]的值，其中1<=i<=j<=n。
输入
第一行一个正整数n（1<=n<=10000），代表数据个数。
接下来一行是n个数据。
接下来一行一个正整数m，代表m个操作。
接下来m行，每行一个操作，格式如上所述。
输出
第一行输出创建后的树状数组，数据之间以空格分隔。
接下来m行，输出m个操作结果：对每个“C i dt ”操作，输出更新后的树状数组，数据间以空格分隔；对每个“Q i j ”操作，输出一个数值。
样例输入
10
1 3 2 6 7 -2 5 8 4 10
5
Q 1 10
C 2 4
Q 2 6
C 6 -3
Q 6 6
样例输出
1 4 2 12 7 5 5 30 4 14
44
1 8 2 16 7 5 5 34 4 14
20
1 8 2 16 7 2 5 31 4 14
-5
题解
#include<iostream> using namespace std; int treeNode[10005] = {0}; int length; int lowbit(int num) { return num & (-num); } int query(int index) { int ans = 0; while (index > 0) { ans += treeNode[index]; index -= lowbit(index); } return ans; } void change(int index, int value) { while (index <= length) { treeNode[index] += value; index += lowbit(index); } } void display() { cout << treeNode[1]; for (int i = 2; i <= length; i++) { cout << " " << treeNode[i]; } cout << endl; } int main() { cin >> length; int *num = new int[length + 1]; for (int i = 1; i <= length; i++) { num[i] = 0; treeNode[i] = 0; } for (int i = 1; i <= length; i++) { cin >> num[i]; change(i, num[i]); } display(); int n; char ope; cin >> n; while (n--) { cin >> ope; if (ope == 'Q') { int startIndex, endIndex; cin >> startIndex >> endIndex; cout << query(endIndex) - query(startIndex - 1) << endl; } else { int index, value; cin >> index >> value; change(index, value); display(); } } return 0; }
2. 逆序对
题目描述
给你n个数，每个数a[i]都是不超过1 0 9 10^910
9
的非负整数。求其中逆序对的个数，即所有这样的数对（i , j )满足1<=i<j<=n且a[i]>a[j]。要求用树状数组的相关操作完成题目。
输入
第一行一个正数n（1<=n<=100000），表示数据的个数。
接下来一行是n个整数。
输出
第一行一个整数m，代表逆序对的个数。
样例输入
5
4 7 2 10 9
样例输出
3
题解
#include<iostream> using namespace std; int treeNode[10005] = {0}; int length; int lowbit(int num) { return num & (-num); } int query(int index) { int ans = 0; while (index > 0) { ans += treeNode[index]; index -= lowbit(index); } return ans; } void change(int index, int value) { while (index <= length) { treeNode[index] += value; index += lowbit(index); } } void display() { cout << treeNode[1]; for (int i = 2; i <= length; i++) { cout << " " << treeNode[i]; } cout << endl; } int getValue(int num) { return query(num) - query(num - 1); } int main() { cin >> length; int *num = new int[length + 1]; for (int i = 1; i <= length; i++) { num[i] = 0; treeNode[i] = 0; } for (int i = 1; i <= length; i++) { cin >> num[i]; change(i, num[i]); } int count = 0; for (int i = 1; i <= length; i++) { for (int j = i + 1; j <= length; j++) { if (getValue(i) > getValue(j)) { count++; } } } cout << count << endl; return 0; }
3.矩阵操作
题目描述
给定一个n✖n的矩阵A，其中每个元素不是0就是1。A[i,j]表示在第i行、第j列的数，初始时，A[i,j]=0 (1<=i,j<=n)。
我们可以按照如下方式改变矩阵：给定一个左上角在（x1,y1)、右下角在(x2,y2)的矩形，通过使用“not”操作改变这个矩形内的所有元素值（元素0变成1，元素1变成0）。为了维护矩阵的信息，你需要写个程序来接收并且执行以下两个操作：
（1）C x1 y1 x2 y2 (1<=x1<=x2<=n, 1<=y1<=y2<=n)，表示更新操作，将改变左上角为（x1，y1）、右下角为（x2，y2）的矩形区域内的数据值，若元素值为0，则变成1；若元素值为1，则变成0。
（2）Q x y (1<=x,y<=n)，表示询问操作，询问A[x,y]的值。
输入
第一行两个整数n和T（2<=n<=1000, 1<=T<=50000)，分别代表方阵大小和操作数。
接下来T行，每行包含一个操作，以“C x1 y1 x2 y2”或者“Q x y”的形式给出，具体描述如上。
输出
对每个询问操作，输出一行一个整数，表示相应矩阵元素的值。
样例输入
2 10
C 2 1 2 2
Q 2 2
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1
样例输出
1
0
0
1
提示
一般的，树状数组是处理查询一个区间、修改一个点，而本题是要处理查询一个点、修改一个区间。在修改区间的时候，可以考虑容斥原理。修改时加一个tag，修改偶数次相当于未修改。
题解
#include<iostream> using namespace std; int treeNode[1005][1005] = {0}; int length; int lowbit(int num) { return num & (-num); } int query(int index) { int ans = 0; while (index > 0) { ans += treeNode[index][index]; index -= lowbit(index); } return ans; } void change(int index, int value) { while (index <= length) { treeNode[index][index] += value; index += lowbit(index); } } void display() { cout << treeNode[1]; for (int i = 2; i <= length; i++) { cout << " " << treeNode[i]; } cout << endl; } int main() { cin >> length; int n; cin >> n; for (int i = 1; i <= length; i++) { for (int j = i; j <= length; j++) { treeNode[i][j] = 0; } } while (n--) { string ope; cin >> ope; if (ope == "C") { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; for (int i = x1; i <= x2; i++) { for (int j = y1; j <= y2; j++) { if (treeNode[i][j] == 0) { treeNode[i][j] = 1; } else { treeNode[i][j] = 0; } } } } if (ope == "Q") { int x, y; cin >> x >> y; cout << treeNode[x][y] << endl; } } return 0; }
