数据结构---树状数组(持续更新)

前言

关于树状数组是什么，我在之前的blog里写过
树状数组是什么?
先敲出一个框架先之后我将慢慢填充

树状数组的基础操作

基本操作

一、lowbits操作

  所有操作的高速公路，用来连接树状数组中两个区间

点击查看代码

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

二、pushup()操作

  通过lowbits向上传参，包含增加区域的每一个大区间都加k。为了能和线段树关联记忆，所以我选择pushup这个函数名。

点击查看代码

void pushup(int *s ,int x,int k){
  while(x<=n){
    s[x]+=k;
    x+=lowbit(x);
  }
}

三、query()操作

  通过lowbit向下查找，把总和加起来

点击查看代码

int query(int *s,int x){
  int t=0;
  while(x){
    t+=s[x];
    x-=lowbit(x);
  }
  return t;
}

基础用法

一、单点更新、区间求和

  原生树状数组的功能就是单点修改，区间求和
洛谷树状数组模板题
代码

点击查看代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
// #define int long long
const int N = 5e5 + 5;

int tree[N];
int n, m;
int lowbits(int x)
{
  return x & -x;
}

void pushup(int x, int k)
{
  while (x <= n)
  {
    tree[x] += k;
    x += lowbits(x);
  }
}

int query(int x)
{
  int res = 0;
  while (x)
  {
    res += tree[x];
    x -= lowbits(x);
  }
  return res;
}

signed main()
{
  IOS;
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    int x;
    cin >> x;
    pushup(i, x);
  }
  while (m--)
  {
    int op, x, y;
    cin >> op >> x >> y;
    if (op == 1)
    {
      pushup(x, y);
    }
    else
    {
      cout << query(y) - query(x - 1) << "\n";
    }
  }

  return 0;
}

二、区间更新、单点求和

  利用差分思想，实现区间更新，又因为query查找的是一段区间的和。所以原来差分数组构成的树状数组查找的就是对应单个点的值
树状数组2

点击查看代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
// #define int long long
const int N = 5e5 + 5;

struct BIT
{
  int tree[N];
  int n;
  int lowbits(int x)
  {
    return x & -x;
  }

  void pushup(int x, int k)
  {
    while (x <= n)
    {
      tree[x] += k;
      x += lowbits(x);
    }
  }

  int query(int x)
  {
    int res = 0;
    while (x)
    {
      res += tree[x];
      x -= lowbits(x);
    }
    return res;
  }
};


signed main()
{
    IOS;
    int n, m;
    cin >> n >> m;
    BIT bit;
    bit.n = n;
    memset(bit.tree, 0, sizeof(bit.tree)); 
    
    int last = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        int diff = x - last;
        bit.pushup(i, diff);
        last = x;
    }
    
    while (m--) {
        int op, x, y, k; 
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> k;
            bit.pushup(x, k);
            bit.pushup(y + 1, -k);
        } else {
            cin >> x;
            cout << bit.query(x) << "\n";
        }
    }
    return 0;
}

三、区间更新、区间求和

四、二维单点更新、区间求和

五、二维区间更新、单点求和

六、二维区间更新、区间求和

树状数组进阶

前缀极值

权值树状数组

离散化

树上二分