个人模板 树状数组

单点更新，查询区间和 const int N = 50000 + 10; int t, n , p = 0; int a[N], c[N]; int lowbit(int x){ return x & (-x); } void update(int x, int val){ while(x <= n){ c[x] += val; x += lowbit(x); } } int query(int x){ int ans = 0; while(x > 0){ ans += c[x]; x -= lowbit(x); } return ans; }

单点更新，查询最值

const int N = 2e5 + 10; int n, m; int c[N], a[N]; int lowbit(int x){ return x & (-x); } void init(){ for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); c[i] = a[i]; for(int j = 1; j < lowbit(i); j <<= 1){ c[i] = max(c[i], c[i-j]); } } } void update(int x, int val){ a[x] = val; for(int i = x; i <= n; i += lowbit(i)){ c[i] = a[i]; for(int j = 1; j < lowbit(i); j <<= 1){ c[i] = max(c[i], c[i-j]); } } } int query(int l, int r){ int ans = a[r]; while(l != r){ for(r -= 1; r - lowbit(r) >= l; r -= lowbit(r)){ ans = max(ans, c[r]); } ans = max(ans, a[r]); } return ans; }