P3368 【模板】树状数组 2

树状数组介绍 ：Binary Indexed Trees structure

题目描述

已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数数加上 xx；
  2. 求出某一个数的值。

板子…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
const int MAX=500000+10;
int n,m,t,x,y,k,a[MAX],b[MAX];
int tree[MAX];
// getsum( r ) - getsum( l - 1 )
int getsum(int i){
	int sum=0;
	while(i>0){
		sum += tree[i];
		i-=(i&-i);
	}
	return sum;
}
//单点修改
void update(int i,int val){
	while(i<=n){
		tree[i]+=val;
		i+=(i&-i);
	}
}
//区间修改
void updateLR(int l,int r,int val){  
	update(l,val);
	update(r+1,-val);
}
// O(n) 建树
void init(){
	fi(i,1,n+1){
		tree[i]+=a[i];
		int j=i+(i&(-i));
		if(j<=n)  tree[j]+=tree[i];
	}
}
//等比放缩 
void scale(int c){
    for (int i = 1 ; i <= n ; i++)
        tree[i] = tree[i] / c;
}
//权值树状数组查询第k小
int kth(int k) {
  int cnt = 0, ret = 0;
  for (int i = log2(n); ~i; --i) {      // i与上文depth含义相同
    ret += 1 << i;                      //尝试扩展
    if (ret >= n || cnt + tree[ret] >= k)  //如果扩展失败
      ret -= 1 << i;
    else
      cnt += tree[ret];  //扩展成功后 要更新之前求和的值
  }
  return ret + 1;
}
//O(log n) 
int getone(int i){
	int sum = tree[i]; 
	if (i > 0){ 
		int z = i - (i & -i);
		i--; 
		while (i != z){ 
			sum -= tree[i]; 
		    i -= (i & -i);
		}
	}
	return sum;
}
int main(){
	freopen("in","r",stdin);
	sf(n);sf(m);
	fi(i,1,n+1){
		sf(b[i]);
		a[i]=b[i]-b[i-1]; //差分
	}
	init();
	while(m--){
		sf(t);
		if(t==1){
			sf(x);sf(y);sf(k);
			updateLR(x,y,k);
		}else if(t==2){
			sf(x);
			pf(getsum(x));
			pfc("\n");
		}
	}
	return 0;
}