树状数组

想出树状数组的大佬真是个天才

将需要求和的数组分布在叶子节点上，A1 - A8

在这里我们引进一个知识点 lowbit   他求的是x的二进制最低位的1后面跟了几个0的长度的2次幂

举个例子 1000001000，这个二进制最低位的1跟了3个0，那么他的lowbit就等于2的3次幂

开一个C数组   将他里面的值等于C[i] = A[i - lowbit(i) + 1] + A[i - lowbit(i) + 2] +... + A[i];

当C数组有了的时候你会很惊讶的发现求和会十分巧妙     sum（7）  ==  sum（111）111代表的是7 的二进制

sum(111) = C(111) + C(110) + C(100)刚好是sum（7）的值（这也太巧妙了吧）

作为蒟蒻我就解释到这里了（why和zjp大佬看了别笑我，因为我真的是个垃圾）

下面就是我的单点更新，区间求和和区间修改以及求逆序对的板子

下面是单点修改和区间求和

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll maxn = 1e6 + 7;

ll a[maxn],c[maxn],n,m;
ll lowbit(ll x)
{
    return x & -x;
}

ll getsum(ll x)
{
    ll sum = 0;
    for(int i = x; i > 0; i -= lowbit(i))
    {
        sum += c[i];
    }
    return sum;
}

void update(ll x,ll y)
{
    for(int i = x; i <= n; i += lowbit(i))
    {
        c[i] += y;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
    	cin >> a[i];
    	update(i,a[i]);
    }
    
    while(m--)
    {
        ll x,y,q;
        cin >> q >> x >> y;
        if(q == 2)
        {
            cout << getsum(y) - getsum(x - 1) << endl;
        }
        else
        {
            update(x,y);
        }
    }
    
    return 0;
}

至于区间修改我们需要用到差分的思想用一个数组维护一下[l,r]是区间，C[l] += k；C[r + 1] -= k; 

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll maxn = 1e6 + 7;

ll a[maxn],c[maxn],n,m;
ll lowbit(ll x)
{
    return x & -x;
}

ll getsum(ll x)
{
    ll sum = 0;
    for(int i = x; i > 0; i -= lowbit(i))
    {
        sum += c[i];
    }
    return sum;
}

void update(ll x,ll y)
{
    for(int i = x; i <= n; i += lowbit(i))
    {
        c[i] += y;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
    	cin >> a[i];
    }
    
    
    while(m--)
    {
        ll x,y,q,k;
        cin >> q;
        if(q == 1)
        {
            cin >> x >> y >> k;
            update(x,k);
            update(y + 1,-k);
        }
        else
        {
            ll sum = 0;
            cin >> x;
            cout << getsum(x) + a[x] << endl;
        }
    }
    
    return 0;
}

对于求逆序对我们可以在当前位置插入他的value值对他之前的点区间求和，在用当前位置减去它的个数就是比它大的个数

相当于将上面代码的update更新的时候变成update（a[i],1) i - getsum（a[i])当前就是逆序对的个数