lowbit运算

二进制数右端第一位1的位权
lowbit(x) = x&(-x)

定义、查询、修改

树状数组是一种支持 单点修改 和 区间查询 的，代码量小的数据结构。
初步感受————oi_wiki
管辖区间
我们记 x 二进制最低位 1 以及后面的 0 组成的数为 lowbit(x)，那么 c[x] 管辖的区间就是 [x-lowbit(x)+1, x]

树状数组1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 5e5+10;

ll a[N];   //原数组
ll c[N];    //树状数组
int n,q;

//O(log n)
ll query(int x)   //区间查询求和 a[1...x]
{
    ll sum=0;
    for(;x;x-=x&(-x))
    {
        sum+=c[x];
    }
    return sum;
}

//O(log n)
void modify(int x,ll s)   //单点修改 a[x]+=s
{
    for(;x<=n;x+=x&(-x))
    {
        c[x]+=s;
    }
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        modify(i,a[i]); //a[i]+=a[i],一开始a[i]=0,初始化赋值
    }
    for(int i=0;i<q;i++)
    {
        int ty;
        scanf("%d",&ty);
        if(ty==1)//修改
       {
            int x,d;
            scanf("%d%d",&x,&d);
            modify(x,d);
            //a[x]+=d; //修改a[x]
        }
        else //查询
        {
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(y)-query(x-1));
        }
    }
    return 0;
}

树状数组2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long u64; //ans对2^64取模，则用无符号整型溢出
const int N = 5e5+10;
int n,q;

// Binary Index Tree -> BIT
// Fenwick's Tree
// 树状数组 
template<class T>   //模板封装，便于使用
struct BIT
{
    T c[N];
    int size;
    void resize(int sum){size=sum;}
    //O(log n)
    T query(int x)   //区间查询求和 a[1...x]
    {
        assert(x<=size);
        T sum=0;
        for(;x;x-=x&(-x))
        {
            sum+=c[x];
        }
        return sum;
    }

    //O(log n)
    void modify(int x,T s)   //单点修改 a[x]+=s
    {
        assert(x!=0);
        // [x!=0]树状数组下标不能有0，否则出现死循环
        for(;x<=n;x+=x&(-x))
        {
            c[x]+=s;
        }
    }
};
BIT <u64> c1,c2;    
//c1：d[i]原数组的差分数组， c2:i*d[i]的差分数组
//d[],原数组

int main()
{
    scanf("%d%d",&n,&q);
    c1.resize(n);
    c2.resize(n);
    for(int i=1;i<=n;i++)
    {
        int a;
        scanf("%llu",&a);
        c1.modify(i,a);
        c1.modify(i+1,-a);
        c2.modify(i,i*a);
        c2.modify(i+1,(i+1)*(-a));
    }

    for(int i=0;i<q;i++)
    {
        int ty;
        scanf("%d",&ty);
        if(ty==1)//修改
        {
            int l,r;
            u64 d;
            scanf("%d%d%llu",&l,&r,&d);
            c1.modify(l,d);   //d[l]+=d
            c1.modify(r+1,-d);  //d[r+1]-=d
            c2.modify(l,l*d);
            c2.modify(r+1,(r+1)*(-d));
        }
        else //查询c1[x]
        {
            int x;
            scanf("%llu",&x);
            u64 ans=c1.query(x);
            printf("%llu\n",ans);
        }
    }
    return 0;
}

区间修改+查询前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long u64; //ans对2^64取模，则用无符号整型溢出
const int N = 201000;
int n,q;

// Binary Index Tree -> BIT
// Fenwick's Tree
// 树状数组 
template<class T>   //模板封装，便于使用
struct BIT
{
    T c[N];
    int size;
    void resize(int sum){size=sum;}
    //O(log n)
    T query(int x)   //区间查询求和 a[1...x]
    {
        assert(x<=size);
        T sum=0;
        for(;x;x-=x&(-x))
        {
            sum+=c[x];
        }
        return sum;
    }

    //O(log n)
    void modify(int x,T s)   //单点修改 a[x]+=s
    {
        assert(x!=0);
        // [x!=0]树状数组下标不能有0，否则出现死循环
        for(;x<=n;x+=x&(-x))
        {
            c[x]+=s;
        }
    }
};
BIT <u64> c1,c2;    //c1：d[i]差分数组， c2:i*d[i]差分数组
//d[]原数组

int main()
{
    scanf("%d%d",&n,&q);
    c1.resize(n);
    c2.resize(n);

    for(int i=0;i<q;i++)
    {
        int ty;
        scanf("%d",&ty);
        if(ty==1)       //区间修改
        {
            int l,r;
            u64 d;
            scanf("%d%d%llu",&l,&r,&d);
            c1.modify(l,d);   //d[l]+=d
            c1.modify(r+1,-d);  //d[r+1]-=d
            c2.modify(l,l*d);
            c2.modify(r+1,(r+1)*(-d));
        }
        else        //查询d[x]的前缀和
        {
            int x;
            scanf("%llu",&x);
            u64 ans=(x+1)*c1.query(x)-c2.query(x);
/*
d[1]=c1
d[2]=c1+c2
d[3]=c1+c2+c3
......
d[x]前缀和=d[1]+d[2]+...+d[x]=x*c1+(x-1)*c2+...+cx
即 i=(1~x),对(x+1-i)c[i]求和
即 (x+1)*(i=(1~x)对c[i]求和) - i=(1~x)对i*c[i]求和
*/
            printf("%llu\n",ans);
        }
    }
    return 0;
}

区间查询

1
2
3
4
5
6
7
8
9
10
11
12
13
//O(log n)
ll query(int x)   //区间查询求和 a[1...x]
{
    ll sum=0;
    for(;x;x-=x&(-x))
    {
        sum+=c[x];
    }
    return sum;
}

//查询x~y
query(y)-query(x-1);

单点修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//O(log n)
void modify(int x,ll s)   //单点修改 a[x]+=s
{
    for(;x<=n;x+=x&(-x))
    {
        c[x]+=s;
    }
}

//将a[i]+=d
modify(x,d);   //修改c[i]
a[x]+=d; //修改a[x]
//将a[i]=d
modify(x,d-a[x]);   //a[x]——>d,修改c[i]
a[x]=d; //修改a[x]

xxxxxxxxxx ​​C++

差分

单点查询

前缀和之差：query(x)-query(x-1);
差分应用： c1.query(x) / c[x]=d1+d2+..+dx

逆序对

i<j && a[i]>a[j]

树状数组解法

1 扫描线：静态——>动态
2 对权值开树状数组(后缀和查询——>前缀和查询)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e5+10;

int tree[N],ranks[N],n;
ll ans;
struct point
{
    int num,val;
}a[N];

inline bool cmp(point x,point y)
{
    if(x.val==y.val)    return x.num<y.num;
    return x.val<y.val;
}

//O(log n)
ll query(int x)   //区间查询求和 a[1...x]
{
    ll sum=0;
    for(;x;x-=x&(-x))
    {
        sum+=tree[x];
    }
    return sum;
}

//O(log n)
void modify(int x,ll s)   //单点修改 a[x]+=s
{
    for(;x<=n;x+=x&(-x))
    {
        tree[x]+=s;
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i].val);
        a[i].num=i;
    }
    sort(a+1,a+n+1,cmp);    //排序，数值从小到大，数值相同则序号小在前
    for(int i=1;i<=n;i++)
    {
        ranks[a[i].num]=i;  //ranks[原序号]=现排序  (将数组转化为1~n)
    }
    for(int i=1;i<=n;i++)
    {
        modify(ranks[i],1);
        ans+=i-query(ranks[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

归并解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// [](https://www.luogu.com.cn/problem/P1908)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e5+10;

void solve()
{
    int n;
    cin>>n;
    vector<ll> a(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    ll ans=0;
    auto dfs=[&](auto dfs,int s,int t)->void
    {
        if(s>=t)    return;
        int mid=s+t>>1;
        dfs(dfs,s,mid),dfs(dfs,mid+1,t);    //两半排序(从小到大)
        vector<ll> f(a.begin()+s,a.begin()+mid+1),     //f，g两个有序数列
                    g(a.begin()+mid+1,a.begin()+t+1);
        for(ll i=0,j=0,p=s;i<f.size() || j<g.size();)
        {
            if(i>=f.size()) a[p++]=g[j++];
            else if(j>=g.size())    a[p++]=f[i++];
            else if(f[i]<=g[j])     a[p++]=f[i++];
            else    a[p++]=g[j++],ans+=f.size()-i;
        }
    };
/*
例如：
f：i   1 3 4
g：j   2 5 7
    f[0]<g[0] i++
    f[1]>g[0] j++,且f中前i个数小于g[0],f中f[i]及以后的数大于g[0],
              故g[0]与f[i]及以后的数构成逆序对，即2与3,4
*/  
    dfs(dfs,1,n);
    cout<<ans<<endl;
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t=1;
//    cin>>t;
    while(t--)
    {
        solve();
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// [](https://codeforces.com/contest/1983/problem/D)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;

int a[N], b[N], c[N];
ll sum1, sum2;
void mergesort(int l, int r, int a[], ll& ans)
{
    if (l >= r)    return;
    int mid = (l + r) / 2, i = l, j = mid + 1, k = l;
    mergesort(l, mid, a, ans), mergesort(mid + 1, r, a, ans);
    while (i <= mid && j <= r)
        if (a[i] > a[j])
            c[k++] = a[j++], ans += mid - i + 1;
        else
            c[k++] = a[i++];
    while (i <= mid)
        c[k++] = a[i++];
    while (j <= r)
        c[k++] = a[j++];
    for (int i = l; i <= r; i++)
        a[i] = c[i];
    return;
}

void deer()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)  cin >> a[i];
    for (int i = 0; i < n; ++i)  cin >> b[i];
    sum1 = sum2 = 0;
    mergesort(0, n - 1, a, sum1), mergesort(0, n - 1, b, sum2); //归并排序顺便求出逆序对
    // for (int i = 0;i < n;i++)   cout << a[i] << " ";
    // cout << "\n";
    // for (int i = 0;i < n;i++)   cout << b[i] << " ";
    // cout << "\n";
    bool flag = 0;
    for (int i = 0; i < n; ++i)
        if (a[i] != b[i])
        {
            flag = 1;
            break;
        }

    if (flag == 1)  cout << "NO\n";
    else if ((sum1^sum2) & 1)   cout << "NO\n";
    else   cout << "YES\n";
    // cout << sum1 << " " << sum2 << "\n";
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;
    while (t--)
    {
        deer();
    }

    return 0;
}

树状数组上二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 5e5+10;

ll a[N];   //原数组
ll c[N];    //树状数组
int n,q;

//O(log n)
int query(ll x)
{
    ll t=0;
    int pos=0;  //当前走到的位置
    for(int j=18;j>=0;j--)
    {
        if(pos+(1<<j)<=n && t+c[pos+(1<<j)]<=x)
        {
            pos+=(1<<j);
            t+=c[pos];  //1~pos的和
        }
    }
    return pos;
}

/*
int query(lls)
{
    int pos=0;
    for(int j=18;j>=0;j--)
    {
        if(pos+(1<<j)<=n && c[pos+(1<<j)]<=s)
        {
            pos+=(1<<j);
            s-=c[pos];
        }
    }
    return pos;
}

*/

//O(log n)
void modify(int x,ll s)   //单点修改 a[x]+=s
{
    for(;x<=n;x+=x&(-x))
    {
        c[x]+=s;
    }
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        modify(i,a[i]); //a[i]+=a[i],一开始a[i]=0,初始化赋值
    }
    for(int i=0;i<q;i++)
    {
        int ty;
        scanf("%d",&ty);
        if(ty==1)//修改
       {
            int x,d;
            scanf("%d%d",&x,&d);
            modify(x,d-a[x]);   //a[i]->d
            a[x]=d;
        }
        else //查询最大t使a1+a2+...+at<=s
        {
            ll s;
            scanf("%lld",&s);
            printf("%lld\n",query(s));
        }
    }
    return 0;
}

高维树状数组

二维树状数组
n*m个数：a[1,1],a[1,2],a[1,3],…,a[1,m],…,a[n,m]
q个操作：

  1. 1 x y d 修改a[x,y]=d;
  2. 2 x y 查询 i=(1x),j=(1y)的a[i,j]之和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 510;

int n,m,q;
ll a[N][N];   //原数组
ll c[N][N];    //树状数组

//O((log n)^2)
ll query(int x,int y)
{
    ll sum=0;
    for(int p=x;p;p-=p&(-p))
    {
        for(int q=y;q;q-=q&(-q))
        {
            sum+=c[p][q];
        }
    }
    return sum;
}

//O((log n)^2)
void modify(int x,int y,ll s)
{
    for(int p=x;p<=n;p+=p&(-p))
    {
        for(int q=y;q<=m;q+=q&(-q))
        {
            c[p][q]+=s;
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            modify(i,j,a[i][j]);
        }
        
    }
    for(int i=0;i<q;i++)
    {
        int ty;
        scanf("%d",&ty);
        if(ty==1)//修改
       {
            int x,y,d;
            scanf("%d%d%d",&x,&y,&d);
            modify(x,y,d-a[x][y]);
            a[x][y]=d; 
        }
        else //查询
        {
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(x,y));
        }
    }
    return 0;
}