标签：20231121 树状 int lowbit add 数组 op

2023/11/21

树状数组

t[i]，为树状数组；a[i]，为原数组

t[i]代表的区间为a(i-lowbit(i)+1)~a(i)这个区间。

所以求前缀的时候，每次-=lowbit(x),区间是连续接起来的

修改操作，a[x]+val,原数组单点加，那么我们要去树状数组上找哪些节点包含a[x],所以是一个+=lowbit(x)的过程

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 1e6 + 10;
int t[N];
int n, m;
int a[N];

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

void add(int x, int val)  //对a[x]+val,同时修改t数组，t是真实意义上的树状数组
{
    while (x <= n)
    {
        t[x] += val;
        x += lowbit(x);
    }
}

int getsum(int x)    // 计算sum[1,x]  1到x的前缀和 ，a[1]..a[x]的和
{
    int sum = 0;
    while (x)
    {
        sum += t[x];
        x -= lowbit(x);
    }
    return sum;
}

int query(int l, int r)   //区间求和  ， 前缀相减
{
    return getsum(r) - getsum(l - 1);
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        add(i, a[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1)
        {
            add(x, y);
        }
        else
        {
            cout << query(x, y) << endl;
        }
    }
}

树状数组上二分

因为2的幂次的t[i]数组（即i为2的幂次），他表示的区间就是1~i，所以可以利用位运算的贪心策略从高到底的求最大的区间（第一次的区间表示）

t[i]代表的区间为a(i-lowbit(i)+1)~a(i)这个区间。(关键)

O（n*logn）查询小于x时，前缀的最大下标

const int N = 2e6 + 10;
int t[N];
int n, m;
int a[N];

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

void add(int x, int val)
{
    while (x <= n)
    {
        t[x] += val;
        x += lowbit(x);
    }
}

int getsum(int x)
{
    int sum = 0;
    while (x)
    {
        sum += t[x];
        x -= lowbit(x);
    }
    return sum;
}

int query(int s)
{
    int c = 0;   // 记录当前的前缀和
    int pos = 0; // 记录位置
    for (int j = 20; j >= 0; j--)
    {
        if (pos + (1LL << j) <= n && c + t[pos + (1LL << j)] <= s)
        {
            pos += (1LL << j);
            c += t[pos];
        }
    }
    return pos;
}

void solve()
{
    int q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        add(i, a[i]);
    }
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int x, d;
            cin >> x >> d;
            add(x, d - a[x]); // 修改a[x]为d
            a[x] = d;
        }
        else
        {
            int s;
            cin >> s;
            cout << query(s) << endl;
        }
    }
}

二维树状数组

对每一个一位的树状数组节点都看成一个树状数组，这样就形成了二维的树状数组，高位同理

二维树状数组 1：单点修改，区间查询

const int N = 4100;
long long t[N][N];
int n, m;

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

void add(int x, int y, int val)
{
    for (int p = x; p <= n; p += p & (-p))
    {
        for (int q = y; q <= m; q += q & (-q))
        {
            t[p][q] += val;
        }
    }
}

int query(int x, int y)
{
    int sum = 0;
    for (int p = x; p; p -= p & (-p))
    {
        for (int q = y; q; q -= q & (-q))
        {
            sum += t[p][q];
        }
    }
    return sum;
}

void solve()
{
    cin >> n >> m;
    int op;
    while (cin >> op)
    {
        if (op == 1)
        {
            int x, y, k;
            cin >> x >> y >> k;
            add(x, y, k);
        }
        else
        {
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            cout << query(c, d) - query(c, b - 1) - query(a - 1, d) + query(a - 1, b - 1) << endl;
        }
    }
}

标签：20231121,树状,int,lowbit,add,数组,op
From： https://www.cnblogs.com/chenchen336/p/17847792.html