ACM-树状数组基础

ACM- 树状数组

img

我们约定：把上图中参差不齐的白色方格称为 数组$C$，没个$C$都支配着几个数字。

同时，最下面一行的数字所构成的数组为数组$a$.

例如：C[2]管理的是 a[1],a[2].

C[4]管理的是a[1],a[2],a[3],a[4].

C[6]管理的是a[5],a[6].

C[8]管理的是a[1],a[2],a[3],a[4],a[5]……a[8].

操作函数

1.lowbit()

1
2
3
4
5
int lowbit(int x) 
{
  //算出x二进制的从右往左出现第一个1以及这个1之后的那些0组成数的二进制对应的十进制的数
  return x & -x;
}

意义：它可以求出数组c[x]管理几个数组a中的数。

不难发现，每一个C[i]一定管理的数组a的下表的上限就是a[i]，那么往后找几个数呢，才是C[i]真正的管理范围呢？

此时lowbit()函数就派上了用场，我们知道一个数组C[i]所管理的右端点，而且通过lowbit（i）我们就可以知道C[i]管理了几个数，因此我们就可以知道这个数组C[i]

还是举上图的例子，比如所管理的范围了。

2.add（x,k）单点修改a[x]=a[x]+k

1
2
3
4
5
6
void add(int x, int k) {
  while (x <= n) {  //不能越界
    c[x] = c[x] + k;
    x = x + lowbit(x);
  }
}

怎么理解这个函数呢？

单点修改后我们就要维护数组C的值了，具体维护哪些数组C呢，又怎么找到这些数组C呢？

比如 a[4]要加上一个数k，C[4]肯定管理着a[4]，C[4]之前的C[i] (i=1.2.3)肯定管理不到a[4]，那么我们只需要往后找。

我们发现C[4+lowbit[4]]也是。

因此我们推广后可以猜到：

c[x] = c[x] + k;
x = x + lowbit(x); 便可以将所有C更新。

同时不要忘记加上边界条件下x<=n ，这样就完成了单点修改。

3.区间求和&&区间加

首先要介绍差分数组：

比如 a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]

​ b[1] b[2] b[3] b[4] b[5] b[6] b[7] b[8]

其中b[i]=a[i]-a[i-1].

可是造出这样的一个数组有什么用呢，我们假如进行区间加的话若对每个数字都操作，这样的复杂度显然是很差的。

我们考虑一下，当我们对数组a区间加上k的时候，所对应的数组b有什么变化呢？

显而易见，数组b大部分还是没变得，只有区间开头和结尾后一个会变。我们举一个例子就显而易见了，比如我们对a[3-6]同时加上k, b[4-6]都没有变，而b[3]=a[3]-a[2]，b[7]=a[7]-a[6],所以这两个都变了，我们只需要维护两个点就行了。

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
int t1[MAXN], t2[MAXN], n;
//t1为维护得第一个数组 t2为维护的第二个数组
inline int lowbit(int x) { return x & (-x); }

void add(int k, int v) {          //维护更新上述的两个数组t1,t2
  int v1 = k * v;
  while (k <= n) {
    t1[k] += v, t2[k] += v1;
    k += lowbit(k);
  }
}

int getsum(int *t, int k) {
  int ret = 0;
  while (k) {
    ret += t[k];       //t[1]+t[2]...+t[k]
    k -= lowbit(k);    //
  }
  return ret;
}

void add1(int l, int r, int v) {
  add(l, v), add(r + 1, -v);       //将区间加差分为两个前缀加
}

long long getsum1(int l, int r) {
  return (r + 1ll) * getsum(t1, r) - 1ll * l * getsum(t1, l - 1) -
      (getsum(t2, r) - getsum(t2, l - 1));
}

4.树状数组的O(n)建树，O（logn）查询第K大/小

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
// O(n)建树
void init() {
  for (int i = 1; i <= n; ++i) {
    t[i] += a[i];
    int j = i + lowbit(i);
    if (j <= n) t[j] += t[i];
  }
}

int kth(int k) {  //权值树状数组查询第k小
  int cnt = 0, ret = 0;
  for (int i = log2(n); ~i; --i) {
    ret += 1 << i;
    if (ret >= n || cnt + t[ret] >= k)
      ret -= 1 << i;
    else
      cnt += t[ret];
  }
  return ret + 1;
}

//时间戳优化add() sum()
int tag[MAXN], t[MAXN], Tag;
void reset() { ++Tag; }
void add(int k, int v) {
  while (k <= n) {
    if (tag[k] != Tag) t[k] = 0;
    t[k] += v, tag[k] = Tag;
    k += lowbit(k);
  }
}
int getsum(int k) {
  int ret = 0;
  while (k) {
    if (tag[k] == Tag) ret += t[k];
    k -= lowbit(k);
  }
  return ret;
}