手推zwk线段树，效率比传统的低，求问

这是窝手推 zwk 线段树写的 P3374 【模板】树状数组 1 的代码，推的大部分地方都和传统的一致，只是查询有所不同。

代码

CPP

#include<bits/stdc++.h>
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define fi first
#define se second
#define in(a) a = read()
using namespace std;
typedef long long ll;
const int Size = 1 << 14;
const int N = 5e5 + 5;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f; 
inline int read() {
	int x = 0;
	char ch = getchar();
	bool f = 0;
	while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();
	while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();
	return f ? -x : x;
}
#define int long long
#define push_up(i) t[i] = t[i << 1] + t[i << 1 | 1]
#define lowbit(x) (x & -x)
int a[N] , t[N << 2] , lg[N << 2] , n , q , m = 1; 
inline int query(int l , int r) {
	int ans = 0;
	l = l + m - 1 , r = r + m - 1;
	while(l <= r){
		int v = min(lg[lowbit(l)] , lg[r - l + 1]);
		ans += t[l >> v];
		l += (1 << v);
	}
	return ans;
}
inline void update(int x , int val) {
	for(int i = x + m - 1 ; i ; i >>= 1) t[i] += val;
}
signed main() {
	//cin_fast;
    in(n) , in(q);
    while(m < n) m <<= 1;
    for(int i = 1 ; i <= n ; i ++) in(a[i]);
    for(int i = 1 ; i <= n ; i ++) t[i + m - 1] = a[i];
    for(int i = m - 1 ; i ; i --) push_up(i);
    for(int i = 2 ; i <= m ; i ++) lg[i] = lg[i >> 1] + 1;
    while(q --) {
    	int op , x , y;
    	in(op) , in(x) , in(y);
    	if(op == 1) update(x , y);
    	else printf("%d\n" , query(x , y));
	}
	return 0;
}

传统 zwk 线段树代码（查询）

CPP

inline int query(int l, int r) {
    int ans = 0;
    l = l + m - 1;
    r = r + m - 1;
    if(l == r) return t[l];
    ans += t[l] + t[r];
    while(l ^ r ^ 1) {
        if(~ l & 1) ans += t[l ^ 1];  
        if(r & 1) ans += t[r ^ 1];   
        l >>= 1, r >>= 1; 
    }
    return ans;
}

也有写成这样的：

CPP

inline int query(int l, int r) {
    int ans = 0;
    l = l + m - 1;
    r = r + m - 1;
    while(l <= r) {
        if(l & 1) ans += t[l++];      
        if(!(r & 1)) ans += t[r--];  
        l >>= 1, r >>= 1;            
    }
    return ans;
}

我的查询

O(\log n)

的复杂度是和子区间数量有关的，传统 zwk 线段树的复杂度是和两区间端点的 LCA 高度有关，虽然同为

O(\log n)

，但我认为前者的复杂度在随机数据下应该更优秀啊，求巨佬解答。

还有一个猜想，是否可以基于传统 zwk 线段树实现

O(1)

的静态查询，理论上来讲是可以像 st 表一样把每个节点往上的

\log n

个信息统计下来的，然后不难证明

l >> \lfloor \log_2(l\oplus r)\rfloor,r >> \lfloor \log_2(l\oplus r)\rfloor

就可以得到两个端点跳到互为兄弟点时的下标，预处理

st[i][j][1/2]

表示左或右端点 i 往上跳

i

个节点的树链值，于是似乎就可以用以下式子求出答案：

merge(st[l][lg[l\oplus r]-1][0],st[r][lg[l\oplus r]-1][1]))

可以特判单点保证正确性，其求 LCA 的优化和二进制优化猫树似乎是一样的，求大佬证明该做法的正确性！

手推zwk线段树，效率比传统的低，求问

讨论操作

回复

相关推荐

手推zwk线段树，效率比传统的低，求问