【模板】树状数组
【LG3374】已知一个数列，你需要进行下面两种操作：
1.将某一个数加上x
2.求出某区间每一个数的和
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
int n, m;
int c[N];
int lowbit(int x){ return x & -x; }
void add(int x, int y){
while(x <= n){
c[x] += y;
x += lowbit(x);
}
}
int query(int x){
int sum = 0;
while(x){
sum += c[x];
x -= lowbit(x);
}
return sum;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
int x;
scanf("%d", &x);
add(i, x);
}
for(int i = 1; i <= m; i++){
int x, y, z;
scanf("%d%d%d", &z, &x, &y);
if(z == 1){
add(x, y);
}
else{
printf("%d\n", query(y)-query(x-1));
}
}
return 0;
}【LG3368】已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数数加上x
2.求出某一个数的和
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
int n, m, last;
int c[N];
int lowbit(int x){ return x & -x; }
void add(int x, int y){
while(x <= n){
c[x] += y;
x += lowbit(x);
}
}
int query(int x){
int sum = 0;
while(x){
sum += c[x];
x -= lowbit(x);
}
return sum;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
int x;
scanf("%d", &x);
add(i, x-last);
last = x;
}
for(int i = 1; i <= m; i++){
int x, y, z, k;
scanf("%d", &z);
if(z == 1){
scanf("%d%d%d", &x, &y, &k);
add(x, k);
add(y+1, -k);
}
else{
scanf("%d", &x);
printf("%d\n", query(x));
}
}
return 0;
}【POJ2155】二维树状数组（本质：区间修改+单点查询）
输入：'C', x1, y1, x2, y2 将子矩阵(x1, y1)-(x2, y2)全部取反
输出：'Q', x1, y1 查询单点(x1, y1)
只有0和1两个状态，所以和一维一样的思路，但可以不用-1，这里+1-1不改变奇偶性，结果&1即可。（当然你-1也不是问题）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N = 1010;
int t, n, m;
int c[N][N];
template <typename T>
T read(){
T N(0), F(1);
char C = getchar();
for(; !isdigit(C); C = getchar()) if(C == '-') F = -1;
for(; isdigit(C); C = getchar()) N = N*10 + C-48;
return N*F;
}
int lowbit(int x){
return x & -x;
}
void modify(int x, int y, int add){
int tmp = y;
while(x <= n){
y = tmp;
while(y <= n){
c[x][y] += add;
y += lowbit(y);
}
x += lowbit(x);
}
}
int query(int x, int y){
int tmp = y, ans = 0;
while(x){
y = tmp;
while(y){
ans += c[x][y];
y -= lowbit(y);
}
x -= lowbit(x);
}
return ans;
}
int main(){
freopen("matrix.in", "r", stdin);
freopen("matrix.out","w",stdout);
int x1, y1, x2, y2;
t = read<int>();
while(t--){
memset(c, 0, sizeof(c));
n = read<int>(); m = read<int>();
char cs;
for(int i = 1; i <= m; i++){
scanf("%c", &cs);
if(cs == 'C'){
x1 = read<int>(); y1 = read<int>(); x2 = read<int>(); y2 = read<int>();
modify(x1, y1, 1);
modify(x1, y2+1, 1);
modify(x2+1, y1, 1);
modify(x2+1, y2+1, 1);
}
else{
x1 = read<int>(); y1 = read<int>();
printf("%d\n", query(x1, y1)&1);
}
}
printf("\n");
}
return 0;
}1、vim替换的两种方式
2、Spring Cloud（2）主要组件应用实例
3、我的WCF之旅（5）：Service Contract中的重载（Overloading）（转载）
4、责任链模式
5、正式生产环境下hadoop集群的DNS+NFS+ssh免password登陆配置