数据结构（荣誉）实验五 树状数组

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]都是不超过$10^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;
}

最后

以上就是娇气钢笔为你收集整理的数据结构（荣誉）实验五 树状数组的全部内容，希望文章能够帮你解决数据结构（荣誉）实验五 树状数组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。