lowbit
就
x&(-x)
树状数组
维护一个数组 a_1,..,a_n ，在 O(logn) 满足以下作用
1.单点加
2.查询前缀和
用c[n]来记录 其实应该满足$$\displaystyle c_i = a_{i - lowbit(i) + 1}$$
以前八个数来看就是：
c[1] = a[1]
c[2] = a[1] + a[2]
c[3] = a[3]
c[4] = a[1] + a[2] + a[3] + a[4]
c[5] = a[5]
c[6] = a[5] + a[6]
c[7] = a[7]
c[8] = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8]
1.单点加
1
2
3
4
5
6
7
8
9
10
11
| #define ll long long
const int N = 201000;
int a[N];
ll c[N];
ll query(int x){
ll s = 0;
for(; x; x -= x & (-x)){
s += c[x];
}
return s;
}
|
2.查询前缀和
1
2
3
4
5
6
7
8
9
| #define ll long long
const int N = 201000;
int a[N];
ll c[N];
void modify(int x,ll s){
for(; x <= n; x += x & (-x)){
c[x] += s;
}
}
|
额外补充：
3.区间加的写法：
1.在区间 [l,r] 内的原数组a 加上 d
易知$$\displaystyle d_{i} = a_{i} - a_{i - 1}$$
如果对**[l , r]** 都加上 x，那么区间内差分数组实际上不会发生改变，实际上只有 $$\displaystyle d[l] += x,d[r + 1] -= x$$
coding:
1
2
3
4
5
6
7
| int l,r;
long long d;
std::cin >> l >> r >> d;
c1.modify(l,d);
c1.modify(r + 1, -d);
c2.modify(l, l * d);
c2.modify(r + 1, (r + 1) * (-d));
|
2.在区间加的情况下进行查询
不难知道：
$$\displaystyle a_1 = d_1$$
$$\displaystyle a_2 = d_1 + d_2$$
$$\displaystyle a_3 = d_1 + d_2 + d_3$$
易发现规律：
$$\displaystyle sum = x * d_1 + (x - 1) d_2 +\cdots + d_x$$
$$\displaystyle = \sum_{i = 1} ^ {x} (x + 1 - i) d_ i$$
$$\displaystyle = (x + 1) * \sum_{i = 1} ^ {x} d_i - \sum_{i = 1} ^ {x} i* d_i$$
coding:
1
| ll ans = (x + 1) * c1.query(x) - c2.query(x)
|
封装的板子如下：
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
| template <class T>
class Fenwick {
const int n;
std::vector<T> a;
public:
Fenwick(int n) : n(n), a(n) { }
void add(int x, T v) {
assert(0 <= x < n);
x ++;
while (x <= n) {
a[x - 1] += v;
x += x & (-x);
}
}
T sum(int x) {
assert(0 <= x < n);
T ans = 0;
while (x > 0) {
ans += a[x - 1];
x -= x & (-x);
}
return ans;
}
T rangeSum(int l, int r) {
assert(0 <= l <= r < n);
return sum(r) - sum(l);
}
};
|
单点修改：
1
2
| void f.add(int x,T v)
a[x] += p;
|
复杂度：O(logN)
区间查询(Sum)：
查询 [0,x) 的区间和
时间复杂度：O(logN)
区间查询(rangeSum)：
1
| T f.rangeSum(int l, int r)
|
查询 [l,r) 的区间元素和
线段树
建树+查询
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| const int N = 201000;
struct node {
int minv;
} seg[N * 4];
void update(int id) {
seg[id].minv = std::min(seg[id * 2].minv, seg[id * 2 + 1].minv);
}
void build(int id,int l,int r){
if (l == r){
seg[id].minv = a[l];
} else {
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
update(id);
}
}
|
单点修改
1
2
3
4
5
6
7
8
9
10
11
12
|
void change(int id, int l, int r, int pos, int val) {
if(l == r){
seg[id].minv = val;
} else {
int mid = (l + r) / 2;
if(pos <= mid) change(id * 2, l, mid, pos, val);
else change(id * 2 + 1, mid + 1, r, pos, val);
update(id);
}
}
|
查询最小值
1
2
3
4
5
6
7
8
9
10
| int query(int id, int l, int r, int ql, int qr) {
if(l == ql && r == qr) return seg[id].minv;
int mid = l + r >> 1;
if(qr <= mid) return query(id * 2, l, mid, ql, qr);
else if(ql > mid) return query(id * 2 + 1, mid + 1, r, ql, qr);
else {
return std::min(query(id * 2, l, mid, ql, mid), query(id * 2 + 1, mid + 1, r, mid + 1, qr));
}
}
|
懒标记