树状数组

原理思想

  1. 利用二进制提高对大数组的操作速度,但存储空间不变,依旧需要开出原数组大小。
  2. 可当做一种快速的前缀和。
  3. 每次更新与每次查找都是O(logn),即更新变慢,但查找速度得到极大的提高。

缺点:无法删除和插入元素

主要函数(lowbit、add、sum)

1.lowbit(int a)

用途:提取数字a的最低位1;

原理:理解a&-a;

代码:

int lowbit(int i) {
    return i&-i;
}

2.add(int x, int d)

用途:在下标x处增加d(可正可负);

原理:利用二进制依次向上进行修改

代码:

void add(int i, int value) {
    while(i<=N) {
        c[i]+=value;
        i=i+lowbit(i);
    }
}

3.sum(int x)

用途:用于求区间1~x的元素之和;

原理:

C[i]=A[i-2^k+1]+A[i-2 ^k+2]+…+A[i](k为i的二进制中最低位到最低位1之间连续零的长度)

代码:

int sum(int i) {
    int sum=0;
    while(i>0) {
        sum+=c[i];
        i-=lowbit(i); // 循环次数等于i的二进制的1的个数
    }
    return sum;
}

模板题(HDOJ 1166 敌兵布阵)

Problem Description
C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动,而Derek每次询问的段都不一样,所以Tidy不得不每次都一个一个营地的去数,很快就精疲力尽了,Derek对Tidy的计算速度越来越不满:"你个死肥仔,算得这么慢,我炒你鱿鱼!”Tidy想:“你自己来算算看,这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下,Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说:“死肥仔,叫你平时做多点acm题和看多点算法书,现在尝到苦果了吧!”Tidy说:"我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼,这么算他真的会崩溃的,聪明的读者,你能写个程序帮他完成这项工作吗?不过如果你的程序效率不够高的话,Tidy还是会受到Derek的责骂的.

Input
第一行一个整数T,表示有T组数据。 每组数据第一行一个正整数N(N<=50000),表示敌人有N个工兵营地,接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人(1<=ai<=50)。 接下来每行有一条命令,命令有4种形式: (1) Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30) (2)Sub i j ,i和j为正整数,表示第i个营地减少j个人(j不超过30); (3)Query i j ,i和j为正整数,i<=j,表示询问第i到第j个营地的总人数; (4)End 表示结束,这条命令在每组数据最后出现; 每组数据最多有40000条命令

Output
对第i组数据,首先输出“Case i:”和回车, 对于每个Query询问,输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。

Sample Input
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End

Sample Output
Case 1:
6
33
59

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;

int N, c[50005];
int lowbit(int i) {
    return i&-i;
}
void add(int i, int value) {
    while(i<=N) {
        c[i]+=value;
        i=i+lowbit(i);
    }
}
int sum(int i) {
    int sum=0;
    while(i>0) {
        sum+=c[i];
        i-=lowbit(i);
    }
    return sum;
}
// 以上为模板函数
int main() {
    int t, Case=0;
    scanf("%d", &t);
    while(t--) {
        printf("Case %d:\n", ++Case);
        scanf("%d", &N);
        memset(c,0,sizeof(c));
        for(int i=1; i<=N; ++i) {
            int d;
            scanf("%d", &d);
            add(i,d);
        }
        char command[15];
        int x, y;
        while(~scanf("%s", command)&&command[0]!='E') {
            scanf("%d%d", &x, &y);
            if(command[0]=='Q') printf("%d\n",sum(y)-sum(x-1));
            else if(command[0]=='A') add(x,y);
            else add(x,-y); // 上文所提到的增加负数
        }
    }
    return 0;
}

二维树状数组

原理:就像运动的可叠加性一样, x,y两个垂直方向的运动互不影响, 因此树状数组也是一样, i,j两个方向同时使用, 得到巨大的速率优化。

Matrix (from PKU)

(这题包含了几个树状数组题的思想)

Problem Description
Given an N*N matrix A, whose elements are either 0 or 1. A[i, j] means the number in the i-th row and j-th column. Initially we have A[i, j] = 0 (1 <= i, j <= N).

We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using “not” operation (if it is a ‘0’ then change it into ‘1’ otherwise change it into ‘0’). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.

  1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2).
  2. Q x y (1 <= x, y <= n) querys A[x, y].

Input
The first line of the input is an integer X (X <= 10) representing the number of test cases. The following X blocks each represents a test case.

The first line of each block contains two numbers N and T (2 <= N <= 1000, 1 <= T <= 50000) representing the size of the matrix and the number of the instructions. The following T lines each represents an instruction having the format “Q x y” or “C x1 y1 x2 y2”, which has been described above.

Output
For each querying output one line, which has an integer representing A[x, y].

There is a blank line between every two continuous test cases.

Sample Input
1
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

Sample Output
1
0
0
1

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#define maxn 1100
using namespace std;
int lowbit(int i){
	return (i&(-i));
}
int c[maxn][maxn], n;
void update(int x, int y, int val){
    	for(; x<=n; x+=lowbit(x))
         for(int i=y; i<=n; i+=lowbit(i))  //此处一定要让i=y, 不能让y变了, 因为y要使用多次
             c[x][i]+=val;
}
int getsum(int x, int y) {
	int sum=0;
	for(; x; x-=lowbit(x))
	  	for(int i=y; i; i-=lowbit(i))  //同样让i=y
	        sum+=c[x][i];
	return sum;
}
int main(){
 int ca;
 cin>>ca;int o=0;
 while(ca--){
 	if(o) puts("");
 	o++;
 	int m;
 	memset(c,0,sizeof(c));
 	scanf("%d%d",&n,&m);
 	while(m--){
 		char str[55];
	 	scanf("%s",str);
	 	if(str[0]=='C'){
	 		int x1, x2, y1, y2;
	 		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
	 		update(x1,y1,1);    //注意体会这几个update。
			update(x2+1,y2+1,1);
			update(x2+1,y1,1);
			update(x1,y2+1,1);
	 	}
	 	else {
	 		int a,d;
	 		cin>>a>>d;
	 		printf("%d\n", getsum(a,d)&1);
	 	}
	 }
 }
}