线段树板子的小修改

Posted by Cww97 on 2018-05-06

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/80213430
关于M的计算方法

1
2
3
int M = 1;
for (; M < n;)M <<= 1;
if (M > 1) M--;

今天读学生代码,小朋友的代码都很规范

1
2
3
4
5
6
7
int M = 1;
for (; M < n;) {
M <<= 1;
}
if (M > 1) {
M--;
}

可是,好长啊,多年前看见主任的几个 log 感觉自己写不出来(当时自己确实写不出来)

现在试试吧 M = (1 << (int)(ceil)(log(i)/log(2))) - 1 ,诺

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void emmm(){
for (int i = 1; i <= 1000000;i++){
int M = 1;
for (; M < i;) {
M <<= 1;
}
if (M > 1) {
M--;
}
int k = (1 << (int)(ceil)(log(i)/log(2))) - 1;
if (k != M){
printf("%d, %d, %d\n", i, M, k);
}
}
}

发现 n=1 的时候不一样,当时加那个 M--if 的时候似乎是在某次cf上,现在脑子一想,好像 n=1 的时候M就该是0

打扰了,告辞

一句话

1
M = (1 << (int)(ceil)(log(i)/log(2))) - 1;

现在板子长这样

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
struct ZKWSegTree{
#define lc (t<<1)
#define rc (t<<1^1)
int sum[N], M;

inline void build(int n){
M = (1 << (int)(ceil)(log(i)/log(2))) - 1;
memset(sum, sizeof(sum), 0);
for (int i = 1+M; i <= n+M; i++){
scanf("%d", &sum[i]);
}
for (int t = M; t >= 1; t--){
sum[t] = sum[lc] + sum[rc];
}
}

void add(int t, int x){
for (sum[t+=M]+=x, t>>=1; t; t>>=1){
sum[t] = sum[lc] + sum[rc];
}
}

int query(int l, int r){
int ans = 0;
for (l+=M-1,r+=M+1; l^r^1; l>>=1,r>>=1){
if (~l&1) ans += sum[l^1];
if ( r&1) ans += sum[r^1];
}
return ans;
}
} T;