树状数组-白红宇

树状数组

阅读量：4460 次

发布时间：2019-06-08

本文共 5962 字，大约阅读时间需要 19 分钟。

最近几天在学树状数组，做一个小总结！

树状数组

引入（应用）
- 给定一个序列，动态的修改某一个数、询问一段数字的和
- 一般算法：修改1次O(1),查询一次O(m),查询n次O(m*n)容易超时

模型

基本定义
- c[i]记录了多少个数的和
  由图：
  C1=a1
  C2=a1+a2
  C3=a3
  C4=a1+a2+a3+a4
  C5=a5
  C6=a5+a6
  ……
  C8=a1+a2+a3+a4+a5+a6+a7+a8
  ……
  C[2^n]=a[1]+a[2]+….+a[2^n]
  可知：
  C[n]表示2^k个数的和（k为n对应的2进制数的末尾0的个数），其中2 ^ k = n & (n ^ n – 1) == n & -n (lowbit函数)
- 如何修改单点
  修改了某个a[i],就需改动所有包含a[i]的c[j]，即修改从子节点到父节点路径上的所有c
  父节点：
  第X项的父（后继）节点是第X + (X & -X)项（由图可分析）
- 如何求和
  求和（前驱和）直接使用一次for循环，循环的次数为x的二进制表示中1的个数，即x前驱就是每次砍掉x二进制的最后一位1后的数

各功能的伪代码

int lowbit(int x){
    //求和范围/    return x & (x ^ (x - 1));}void buildtree(){
    //建立c数组/    for (int i = 1; i <= n; ++i){        int l = lowbit(i);        for (int j = i - l + 1; j <= i; ++j) c[i] += a[j];    }}void add(int k, int d){
    //修改：给k加上d/    if (k > n) return ;    c[k] += d;    add(k + lowbit(k), d);}int sum(int s, int t){
    //求区间s~t的和/    int ans1 = 0, ans2 = 0;    for (int i = t; i >= 1; i -= lowbit(i)) ans1 += c[i];    for (int i = s - 1; i >= 1; i -= lowbit(i)) ans2 += c[i];    return ans1 - ans2;}

练习

基本树状数组的练习

#include 
     
      #include 
      
       #include 
       
        #define MAXN 100100using namespace std;int n, m;int s, t;int k, d;string ch;int a[MAXN], c[MAXN];int lowbit(int x){    return x & (x ^ (x - 1));}void buildtree(){    for (int i = 1; i <= n; ++i){        int l = lowbit(i);        for (int j = i - l + 1; j <= i; ++j) c[i] += a[j];    }}void add(int k, int d){    if (k > n) return ;    c[k] += d;    add(k + lowbit(k), d);}int sum(int s, int t){    int ans1 = 0, ans2 = 0;    for (int i = t; i >= 1; i -= lowbit(i)) ans1 += c[i];    for (int i = s - 1; i >= 1; i -= lowbit(i)) ans2 += c[i];    return ans1 - ans2;}int main(){    scanf("%d", &n);    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);    buildtree();    scanf("%d", &m);    for (int i = 1; i <= m; ++i) {        cin >> ch;        if (ch == "ADD") {            scanf("%d %d", &k, &d);            add(k, d);        }        if (ch == "SUM") {            scanf("%d %d", &s, &t);            printf("%d\n", sum(s, t));        }    }    return 0;}

异或求和问题不清楚的手完一下

#include 
     
      #include 
      
       #include 
       
        #define MAXN 100100using namespace std;int n, m;int l, r;int x, y;bool bj;int a[MAXN];int c[MAXN];int lowbit(int x){    return x & (x ^ (x - 1));}void buildtree(){    for (int i = 1; i <= n; ++i){        int l = lowbit(i);        for (int j = i - l + 1; j <= i; ++j) c[i] ^= a[j];    }}int sum(int l, int r){    int ans1 = 0, ans2 = 0;    for (int i = r; i >= 1; i -= lowbit(i)) ans1 ^= c[i];    for (int i = l - 1; i >= 1; i -= lowbit(i)) ans2 ^= c[i];    return ans1 ^ ans2;}void change(int x, int y){    int ch = sum(1, x) ^ sum(1, x - 1);    for (int i = x; i <= n; i += lowbit(i)) c[i] ^= ch, c[i] ^= y;}int main(){    scanf("%d %d", &n, &m);    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);    buildtree();    for (int i = 1; i <= m; ++i) {        cin >> bj;        if (bj) {            scanf("%d %d", &l, &r);            printf("%d\n", sum(l, r));        }        if (!bj) {            scanf("%d %d", &x, &y);            change(x, y);        }    }    return 0;}

这是一个重点
直接遍历遍数组，每个位置先add（a[i], 1），然后再查询sum(a[i])，即到第i位为止的逆序对个数为（i - sum(a[i])）
注意：c数组初始化均为0

//不用离散化/#include 
     
      #include 
      
       #include 
       
        #define MAXN 10000000using namespace std;int n;int a[MAXN];int c[MAXN];int lowbit(int x) {    return x & (x ^ (x - 1));}void add(int x) {    if (x > 100000) return ;    c[x]++;    add(x + lowbit(x));}long long sum(int x) {    long long y = 0;    for (int i = x; i >= 1; i -= lowbit(i)) y += c[i];    return y;}int main(){    scanf("%d", &n);    long long ans = 0;    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), a[i]++;    for (long long i = 1; i <= n; ++i) {        add(a[i]);        ans += (i - sum(a[i]));    }    printf("%lld", ans);    return 0;}

一道树状数组求逆序对的板子题
与上一题不能用离散化不同,此题数据量较大不用离散化会RE,放上离散化的代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define L 500000 + 10using namespace std;struct node{    int v, pos;}a[L];long long n, ans;int num[L], c[L];inline bool comp(node a, node b) {    return a.v < b.v;}inline int lowbit(int x) { return x & (-x);}inline void add(int x) {    for (int i = x; i <= L; i += lowbit(i)) c[i]++;}inline long long sum(int x) {    long long s = 0;    for (int i = x; i; i -= lowbit(i)) s += c[i];    return s;}int main() {    while (scanf("%d", &n) && n != 0) {        memset(a, 0, sizeof(a));        memset(num, 0, sizeof(num));        memset(c, 0, sizeof(c));        ans = 0;        for (int i = 1; i <= n; ++i) scanf("%d", &a[i].v), a[i].pos = i;        sort(a + 1, a + 1 + n, comp);        for (int i = 1; i <= n; ++i) num[a[i].pos] = i;        for (int i = 1; i <= n; ++i) {            add(num[i]);            ans += (i - sum(num[i]));        }        printf("%lld\n", ans);    }    return 0;}

这道题目的输入数据是多组的
注意可仅根据x坐标来设立c数组
对于每一次+1操作应该操作到最大值MAXN
注意数组的大小也应开到MAXN
一道树状数组基础题……

#include 
     
      #include 
      
       #include 
       
        #define L 20000 + 10#define MAXN 32000 + 5using namespace std;int n, a, b;int ans[MAXN], c[MAXN];int lowbit(int x) {    return x & (-x);}void add(int x) {    while(x <= MAXN){          ++c[x];          x += lowbit(x);      } }int query(int x) {    int q = 0;    while(x > 0){          q += c[x];          x -= lowbit(x);      }    return q;}int main() {    while (scanf("%d", &n) != EOF) {        memset(c, 0, sizeof(c));        memset(ans, 0, sizeof(ans));        for (int i = 1; i <= n; ++i) {            scanf("%d %d", &a, &b);            a++;            ans[query(a)]++;            add(a);        }        for (int i = 0; i < n; ++i)             printf("%d\n", ans[i]);     }    return 0;}