引入
树状数组用于求区间和，其修改和查询的复杂度都是(O(logn))，非常好写，比较小巧。
几种基础用法，关于权值树状数组在另一篇博客。
单点修改，区间查询
区间和
HDU-1166 敌兵布阵
模版：
#include <bits/stdc++.h>
#define N 50005
using namespace std;
typedef long long ll;
int max(int a, int b) {
return a > b ? a : b;
}
int min(int a, int b) {
return a < b ? a : b;
}
int d[N];
int n;
void update(int x, int v) {
for (int i = x; i <= n; i += i & (-i))
d[i] += v;
}
ll query(int x) {
ll ans = 0;
for (int i = x; i; i -= i & (-i))
ans += d[i];
return ans;
}
int main() {
int t;
scanf("%d", &t);
int cnt = 0;
while (t--) {
memset(d, 0, sizeof(d));
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int v;
scanf("%d", &v);
update(i, v);
}
cnt++;
printf("Case %d:
", cnt);
while (1) {
char ch[10];
scanf("%s", ch);
int x, y;
if (ch[0] == 'Q') {
scanf("%d%d", &x, &y);
printf("%lld
", query(y) - query(x - 1));
}
else if (ch[0] == 'A') {
scanf("%d%d", &x, &y);
update(x, y);
}
else if (ch[0] == 'S') {
scanf("%d%d", &x, &y);
update(x, -y);
}
else break;
}
}
return 0;
}
区间最小值
不建议使用树状数组求区间最小值，比较难以理解，而且写起来并不简单
HDU-1754 I Hate It
模版
#include <cstdio>
#include <cstring>
#define N 200050
using namespace std;
int h[N], a[N];
int lowbit(int x) {
return x & (-x);
}
int n, m;
int max(int a, int b) {return a > b ? a : b;}
void update(int x) {
int lx;
while (x <= n) {
h[x] = a[x];
lx = lowbit(x);
for (int i = 1; i < lx; i <<= 1)
h[x] = max(h[x], h[x - i]);
x += lowbit(x);
}
}
int query(int l, int r) {
int ans = 0;
while (r >= l) {
ans = max(a[r], ans);
r--;
for (; r - lowbit(r) >= l; r -= lowbit(r))
ans = max(h[r], ans);
}
return ans;
}
int main() {
while (scanf("%d%d", &n, &m) != EOF) {
memset(h, 0, sizeof(h));
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
update(i);
}
while (m--) {
char ch[2];
int x, y;
scanf("%s%d%d", ch, &x, &y);
if (ch[0] == 'Q') {
printf("%d
", query(x, y));
}
else {
a[x] = y;
update(x);
}
}
}
return 0;
}
单点修改，矩阵求和
直接使用二维树状数组即可。
附：矩阵前缀和求一部分和的公式：
(sumv(x2, y2) - sumv(x1 - 1, y2) - sumv(x2, y11 - 1) + sumv(x1 - 1, y11 - 1))
(sumv(x,y))为从(1,1)到(x,y)的前缀和
题目：HihoCoder-1336 Matrix Sum
模版：
#include <cstdio>
#include <cstring>
#define p 1000000007
#define N 1050
using namespace std;
typedef long long ll;
ll d[N][N];
int n, m;
int lowbit(int x) {
return x & (-x);
}
void update(int x, int y, ll v) {
for (int i = x; i <= n; i += lowbit(i)) {
for (int j = y; j <= n; j += lowbit(j)) {
d[i][j] += v;
}
}
}
ll sumv(int x, int y) {
ll ans = 0;
for (int i = x; i; i -= lowbit(i)) {
for (int j = y; j; j -= lowbit(j)) {
ans += d[i][j];
}
}
return ans;
}
ll query(int x1, int y11, int x2, int y2) {
return sumv(x2, y2) - sumv(x1 - 1, y2) - sumv(x2, y11 - 1) + sumv(x1 - 1, y11 - 1);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
char ch[10];
scanf("%s", ch);
if (ch[0] == 'A') {
int x, y; ll v;
scanf("%d%d%lld", &x, &y, &v);
x++; y++;
update(x, y, v);
}
else {
int x1, y11, x2, y2;
scanf("%d%d%d%d", &x1, &y11, &x2, &y2);
x1++; y11++; x2++; y2++;
printf("%lld
", (query(x1, y11, x2, y2) + p) % p);
}
}
return 0;
}
树状数组求逆序对
使用树状数组维护一个位置之前一共有了多少数，当第i个数a[i]加进来时，先update更新，在询问这个数之前一共有了多少数，使用i-get(a[i])即为对逆序对的贡献，累计即可
题目：洛谷-P1966 火柴排队
此题题意是让a数组和b数组之间每个位置均对应为相同的大小顺序，问最少需要移动几次，即把a的位置移动到b的位置需要移动多少次，排序之后将a映射到b求逆序对即可
模版
#include<bits/stdc++.h>
#define maxn 100060
#define p 99999997
using namespace std;
int c[maxn], d[maxn], n;
inline int getnum(){
char c; int ans = 0; bool flag = false;
while (!isdigit(c = getchar()) && c != '-');
if (c == '-') flag = true; else ans = c - '0';
while (isdigit(c = getchar())) ans = ans * 10 + c - '0';
return ans * (flag ? -1 : 1);
}
struct node{
long long v; int pos;
}a[maxn], b[maxn];
int cmp(node x, node y){
return x.v < y.v;
}
inline int lowbit(int x){
return x & (-x);
}
inline void updata(int x){
while (x <= n){
d[x]++;
x += lowbit(x);
}
}
inline int getsum(int x){
int ans = 0;
while (x > 0){
ans += d[x] % p;
x -= lowbit(x);
}
return ans;
}
int main(){
n = getnum();
for (int i = 1; i <= n; i++){
a[i].v = getnum();
a[i].pos = i;
}
for (int i = 1; i <= n; i++){
b[i].v = getnum();
b[i].pos = i;
}
sort(a + 1, a + n + 1, cmp);
sort(b + 1, b + n + 1, cmp);
for (int i = 1; i <= n; i++){
c[b[i].pos] = a[i].pos;
}
int ans = 0;
for (int i = 1; i <= n; i++){
updata(c[i]);
ans += i - getsum(c[i]);
ans %= p;
}
printf("%d", ans);
return 0;
}