Aczy156

Algorithm11.8 数据结构 树状数组

[TOC]

数据结构 树状数组

https://www.luogu.com.cn/problem/P3374

模版-区间求和(查询)、单点修改(操作)

0、lowbit()看当前节点的归属情况/看当前节点所管辖的节点的个数

eg：8(10) & -8(10) = 8 => 根据树状数组结构图，就是8个节点

eg：4(10) & -4(10) = 4 => 根据树状数组结构图，就是4个节点

eg：6(10) & -6(10) = 2 => 根据树状数组结构图，就是2个节点

![image-20210308181959879](/Users/aczy156/Library/Application Support/typora-user-images/image-20210308181959879.png)

1、单点修改

=> 自下而上修改 => c数组的索引pos从1开始往上找，但是要限定永远≤n => 从下往上找的话，看当前的节点归属那个父节点范围，则需要pos+=lowbit(pos)，此时就可以直接爬升到父节点。

void single_add(int pos, int k) {
  while(pos <= n) {
    c[pos] += k;
    pos += lowbit(pos);
  }
}

2、区间求和「注意这个区间求的是前缀和，也就是1到pos的和。如果区间和的话，可以通过两个前缀和相减得到」

=> 自上而下累加 => c数组的索引pos从target目标开始往下找，但是要限定下限，不能让下限爆掉，pos≥1 => 从上往下累加的话，看当前的节点归属那个的子节点，则需要pos-=lowbit(pos)，此时就可以直接下降到子节点。

int getsum(int pos) {
  int ans = 0;
  while(pos >= 1) {
    ans += c[pos];
    pos -= lowbit(pos);
  }
}

#include <iostream>
using namespace std;
#define maxn 500010
int n, m, tm, tp, ta, tb, c[maxn];

int lowbit(int x) {return x & (-x);}

void single_add(int pos, int k) {
    while (pos <= n) {
        c[pos] += k;
        pos += lowbit(pos);
    }
}

int getsum(int pos) {
    int ans = 0;
    while (pos >= 1) {
        ans += c[pos];
        pos -= lowbit(pos);
    }
    return ans;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {scanf("%d", &tm);single_add(i, tm);}
    while (m--) {
        scanf("%d%d%d", &tp, &ta, &tb);
        if (tp-1) printf("%d\n", getsum(tb)-getsum(ta-1));
        else single_add(ta, tb);
    }
    return 0;
}

模版-区间修改(操作)、单点求和(查询)

区间修改+单点求和 模版：https://www.luogu.com.cn/problem/P3368

区间修改+单次范围最值 【范围最值也可以看作是所有的点取一遍最值】：https://www.luogu.com.cn/problem/P2367

1、区间修改：考虑到差分，之不过是在树上进行差分，利用树状数组进行差分，此时对于树状数组c的修改就只需要修改两头即可了，也就是在l的位置加上k，在r+1的位置减去k，最后再利用树状数组c进行还原即可。

2、此时沿着树状数组进行求和，求的就不是上面的那个区间和了 => 因为这个树状数组代表的是差分，累加所得到的该索引的数组的值。

P3368模版区间修改+多次查询单个点

#include <iostream>
using namespace std;
#define maxn 500010
int n, m, a[maxn], c[maxn], tp, ta, tb, tc;

int lowbit(int x) {return x & (-x);}

void single_add(int pos, int k) {
    while (pos <= n) {
        c[pos] += k;
        pos += lowbit(pos);
    }
}

void interval_add(int l, int r, int k) {
    single_add(l, k);
    single_add(r+1, -k);
}

int getsum(int pos) {
    int ans = 0;
    while (pos >= 1) {
        ans += c[pos];
        pos -= lowbit(pos);
    }
    return ans;
}

int getval(int pos) {
    return a[pos] + getsum(pos);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    while (m--) {
        scanf("%d", &tp);
        if (tp-1) {scanf("%d", &ta);printf("%d\n", getval(ta));}
        else {scanf("%d%d%d", &ta, &tb, &tc);interval_add(ta, tb, tc);}
    }
    return 0;
}

P2367区间修改+最终单次查询所有点

#include <iostream>
using namespace std;
#define maxn 5000010
int n, m, a[maxn], c[maxn], ta, tb, tc, minn = (1<<31)-1; // c为树上的差分数组，a为记录原数据的数组
#define lowbit(x) x&(-x)

void add(int pos, int k) {
    while (pos <= n) {
        c[pos] += k;
        pos += lowbit(pos);
    }
}

void interval_add(int l, int r, int k) {
    add(l, k);
    add(r+1, -k);
}

int query(int pos){
    int ans = 0;
    while (pos >= 1) {
        ans += c[pos];
        pos -= lowbit(pos);
    }
    return ans;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    while (m--) {
        scanf("%d%d%d", &ta, &tb, &tc);
        interval_add(ta, tb, tc);
    }
    for (int i = 1; i <= n; ++i) minn = min(a[i]+query(i), minn);
    printf("%d\n", minn);
    return 0;
}

模版-区间修改(操作)、区间求和(查询)

https://www.luogu.com.cn/problem/P2367

1、区分上面的单点修改+区间求和 // 区间修改+单点查询，都可以解决尾一类问题，核心代码相似，只不过后者就是前者的基础上增添了差分的思想，根据差分用求和来查单点的值 == 根据累加用单点来查求和的值。

2、区间修改+区间查询需要维护两个数组，sum1数组是求和的数组，sum2数组是乘积的数组。进行区间修改的时候，进行差分来修改 // 进行区间查询的时候，根据前缀和来进行查询。

区间修改：

void add(ll pos, ll k) {
    ll tem = k*pos;
    while (pos <= n) {
        sum1[pos] += k;sum2[pos] += tem;
        pos += lowbit(pos);
    }
}

void interval_add(ll l, ll r, ll k) {
    add(l, k);
    add(r+1, -k);
}

区间查询

    ll ans = 0, tem = pos;
    while (pos >= 1) {
        ans += ((tem+1)*sum1[pos] - sum2[pos]);
        pos -= lowbit(pos);
    }
    return ans;
}

ll interval_query(ll l, ll r) {
    return query(r)-query(l-1);
}

完整代码

#include <iostream>
using namespace std;
#define maxn 200010
typedef long long ll;
ll n, m, tm, last, first_val, sum1[maxn], sum2[maxn], tp, ta, tb, tc;
#define lowbit(x) x&(-x)

void add(ll pos, ll k) {
    ll tem = k*pos;
    while (pos <= n) {
        sum1[pos] += k;sum2[pos] += tem;
        pos += lowbit(pos);
    }
}

void interval_add(ll l, ll r, ll k) {
    add(l, k);
    add(r+1, -k);
}

ll query(ll pos) {
    ll ans = 0, tem = pos;
    while (pos >= 1) {
        ans += ((tem+1)*sum1[pos] - sum2[pos]);
        pos -= lowbit(pos);
    }
    return ans;
}

ll interval_query(ll l, ll r) {
    return query(r)-query(l-1);
}

int main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; ++i) {scanf("%lld", &tm);add(i, tm-last);last=tm;}
    while (m--) {
        scanf("%lld", &tp);
        switch (tp) {
            case 1: scanf("%lld%lld%lld", &ta, &tb, &tc);interval_add(ta, tb, tc);break;
            case 2: scanf("%lld", &ta);first_val += ta;break;
            case 3: scanf("%lld", &ta);first_val -= ta;break;
            case 4: scanf("%lld%lld", &ta, &tb);printf("%lld\n", interval_query(ta, tb)+(ta==1)*first_val);break;
            case 5: printf("%lld\n", query(1)+first_val);break;
        }
    }
    return 0;
}

树状数组变式题

https://www.luogu.com.cn/problem/P2345

对个数和坐标轴上的坐标进行维护，维护两个树状数组。

Posted on Feb 1, 2021