https://blog.csdn.net/weixin_43914593/article/details/107842628

树状数组¶

支持单点加，求前缀和。或者单点修改，求前缀max。空间复杂度O(n)

树状数组¶

树状数组（Binary Indexed Tree，BIT，也称为Fenwick Tree）是一种用于高效处理累计和查询和更新的数据结构。它可以在对数时间内完成单点更新和前缀和查询操作。以下是树状数组的实现原理：

基本概念¶

前缀和：数组的前缀和是指从数组的第一个元素到第i个元素的总和。
单点更新：改变数组中某个元素的值。
树状数组：通过一个数组来模拟树形结构，实现对数时间的更新和查询操作。

树状数组的构建¶

树状数组通常用一个一维数组tree来表示，其中tree[i]存储了一部分原数组的元素和。

初始化¶

初始化时，所有的tree[i]都设为0。

vector<int> tree(n + 1, 0);

Lowbit函数¶

树状数组中一个重要的概念是lowbit，它用于找到当前节点直接管辖的区间。

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

lowbit函数返回x在二进制表示下最低位的1所对应的值。

更新操作¶

更新操作用于改变原数组中某个元素的值，并更新树状数组。

首先计算该元素的lowbit，找到需要更新的直接子节点。
然后沿着树向上更新所有相关的节点。

以下是更新操作的伪代码：

void update(int i, int delta) {
    while (i <= n) {
        tree[i] += delta;
        i += lowbit(i);
    }
}

查询操作¶

查询操作用于计算原数组的前缀和。

从给定的索引开始，计算所有包含该索引的父节点的和。
每次查询时，通过lowbit找到下一个需要查询的父节点。以下是查询操作的伪代码：

int query(int i) {
    int sum = 0;
    while (i > 0) {
        sum += tree[i];
        i -= lowbit(i);
    }
    return sum;
}

完整示例¶

假设原数组为arr = [0, 1, 2, 3, 4, 5, 6, 7]，以下是构建树状数组并进行更新和查询的示例：

初始化¶

tree = [0, 0, 0, 0, 0, 0, 0, 0, 0]

更新操作¶

更新arr[3]增加2，即arr[3] = 3 + 2 = 5。

update(3, 2)  // tree变为[0, 0, 0, 1, 1, 1, 2, 2, 2]

查询操作¶

查询前缀和，即arr[1] + arr[2] + arr[3]。

query(3)  // 返回 1 + 2 + 5 = 8

总结¶

树状数组通过使用一个一维数组来模拟树形结构，使得单点更新和前缀和查询都可以在对数时间内完成。它的优点是代码实现简单，空间复杂度低，适用于频繁的更新和查询操作。树状数组不支持区间更新操作，但可以通过一些技巧来扩展这一功能。

再次强调，树状数组的change是**单点加**！！

例题 #1 模板¶

如题，已知一个数列，你需要进行下面两种操作：

将某一个数加上 \(x\)
求出某区间每一个数的和

对于 \(30\%\) 的数据，\(1 \le n \le 8\)，\(1\le m \le 10\)；对于 \(70\%\) 的数据，\(1\le n,m \le 10^4\)；对于 \(100\%\) 的数据，\(1\le n,m \le 5\times 10^5\)。

实现方法¶

关键函数 `lowbit(x)`¶

lowbit(x){return x&-x}

作用： 返回最后一位1的位置

e.g. 对(11010)2执行lowbit返回值为(10)2. x-lowbit(x)操作可快速消去最后一位1

`change(x,v)`¶

在树状数组意义下对x位置进行单点加v。

`query(x)`¶

返回[1,x]的权值和。

应用¶

维护区间加，单点修改

这时我们应该使用change来维护差分数组并且使用query快速求出前缀和。

不可使用change来区间加而query(x)-query(x-1)，因为它根本没这功能！！

代码¶

#include<bits/stdc++.h>
using namespace std;


const int N=5e5+5;
//typedef long long ll;
int n,m,x,y;
int c[N];
int a;


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


void add(int i,int x) {//在位置i加上x
    while(i<=N) {
        c[i]+=x;
        i+=lowbit(i);
    }
}


int sum(int x) {
    int res=0;
    while(x) {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        cin>>a;
        add(i,a);
    }
        //scanf("%d",&a[i]);
    while(m--) {
        int op;
        scanf("%d%d%d",&op,&x,&y);
        if(op==2)
            printf("%d\n",sum(y)-sum(x-1)); //sum(i)求的是a[i]~a[1]的和！！
        else {
            add(x,y);
        }
    }
    return 0;
}

例题 #2 [IOI2019] 排列鞋子¶

Adnan 拥有巴库最大的鞋店。现在有一个装着 \(n\) 双鞋的箱子刚运到他的鞋店。每双鞋是大小相同的两只：一只左脚，一只右脚。Adnan 把这 \(2n\) 只鞋排成一行，该行总共有 \(2n\) 个**位置**，从左到右编号为 \(0\) 到 \(2n-1\) 。

Adnan 想把这些鞋子重新排成**合法的排列**。一个排列是合法的，当且仅当对于所有的 \(i(0\leqslant i \leqslant n - 1)\)，以下条件都成立：

在位置 \(2i\) 和 \(2i+1\) 上的鞋子大小相同；
在位置 \(2i\) 上的鞋子是一只左脚鞋；
在位置 \(2i+1\) 上的鞋子是一只右脚鞋。

为实现上述目标，Adnan 可以做一系列对调。在每次对调中，他选择当前**相邻**的两只鞋进行对调（也就是把它们拿起来，然后将每只鞋子放回到另一只鞋子原来的位置上）。两只鞋子是相邻的，当且仅当其位置编号的差为 \(1\)。

请求出 Adnan 最少要做出多少次对调，才能得到一个合法排列。

输入格式

第一行一个正整数 \(n\)，表示有 \(n\) 双鞋。

第二行 \(2n\) 个整数 \(S_i\)，第 \(i\) 个整数表示位置编号为 \(i-1\) 的鞋子。其中 \(|S_u|\neq 0\)，绝对值表示最初在位置 \(i\) 上的鞋子的大小。如果是负数代表这是一只左脚鞋，否则是右脚鞋。

输出格式

输出一行一个整数，表示最少对调次数。

考虑从后往前匹配。遇到i，就往前找最大的那个-i，将-i向后移动到i之前。

但是我们怎么样统计需要移动几步呢？因为i,-i之间的一些鞋子可能因为被匹配已经移出了i,-i之间了。

这样我们就不应该将它计算在答案内。因此用树状数组标记一下那些鞋子已经被匹配，因为已经被匹配的鞋子一定在i后面而不在当前统计答案的区间内。

/*                                                                                
                      Keyblinds Guide
                    ###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all
      - Alt+la/ra : move mouse to pre/nxt pos'

*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first

// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
    if constexpr (enable_dbg){
    cerr << s;
    if(1)cerr<<' ';
        if constexpr (sizeof...(Args))
            dbg(args...);
    }
}

#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;



/*
策略：
考虑从后往前匹配。遇到i，就往前找最大的那个-i，向后移动。
但是我们怎么样统计需要移动几步呢？因为i,-i之间的一些鞋子可能因为被匹配已经移出了i,-i之间了
这样我们就不应该记录它。因此用树状数组标记一下。
*/

int s[N];
vector<int> e[N];


namespace ctree{
    int c[N];
    inline int lowbit(int x){
        return x&-x;
    }
    int query(int x){
        int res=0;
        while(x){
            res+=c[x];
            x-=lowbit(x);
        }
        return res;
    }
    void change(int x,int v){
        while(x<N){
            c[x]+=v;
            x+=lowbit(x);
        }
    }
}using namespace ctree;


bitset<N> vis;

void solve(){
    int n=rd;
    for(int i=1;i<=n*2;i++){
        s[i]=rd;
        e[n+s[i]].pb(i);
    }
    for(int i=1;i<=n*2;i++){
        change(i,1);
    }

    itn ans=0;

    for(int i=n*2;i;i--){
        if(vis[i])continue;
        vis[i]=1;
        e[n+s[i]].pop_back();
        int pre=e[n+-s[i]].back();
        vis[pre]=1;
        e[n+-s[i]].pop_back();
        ans+=query(i)-query(pre)-1;
        if(s[i]<0)ans++;
        change(pre,-1);
    }


    cout<<ans<<endl;

}

signed main() {
    // freopen(".in","r",stdin);
    // freopen(".in","w",stdout);

    int T=1;
    while(T--){
        solve();
    }
    return 0;
}

练习 #1 贪婪大陆¶

小 FF 最后一道防线是一条长度为 \(n\) 的战壕，小 FF 拥有无数多种地雷，而 SCV 每次可以在 \([L, R]\) 区间埋放同一种不同于之前已经埋放的地雷。由于情况已经十万火急，小 FF 在某些时候可能会询问你在 \([L',R']\) 区间内有多少种不同的地雷，他希望你能尽快的给予答复。

入格式

第一行为两个整数 \(n\) 和 \(m\)，\(n\) 表示防线长度，\(m\) 表示 SCV 布雷次数及小 FF 询问的次数总和。

接下来有 \(m\) 行，每行三个整数 \(q,l,r\)：

若 \(q=1\)，则表示 SCV 在 \([l, r]\) 这段区间布上一种地雷；
若 \(q=2\)，则表示小 FF 询问当前 \([l, r]\) 区间总共有多少种地雷。

输出格式

对于小 FF 的每次询问，输出一个答案（单独一行），表示当前区间地雷总数。

对于 \(100\%\) 的数据，\(0 \le n\)，\(m \le 10^5\)。

考虑标记区间的L和R。一次询问的答案=询问区间内和前面的L-区间前的R

树状数组¶

树状数组¶

基本概念¶

树状数组的构建¶

初始化¶

Lowbit函数¶

更新操作¶

查询操作¶

完整示例¶

初始化¶

更新操作¶

查询操作¶

总结¶

例题 #1 模板¶

实现方法¶

关键函数 lowbit(x)¶

change(x,v)¶

query(x)¶

应用¶

代码¶

例题 #2 [IOI2019] 排列鞋子¶

练习 #1 贪婪大陆¶

关键函数 `lowbit(x)`¶

`change(x,v)`¶

`query(x)`¶