算法提高课第五章树状数组

树状数组和差分树状数组

• 快速求前缀和
• 修改某个数

241. 楼兰图腾 - AcWing题库

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 200010;

int n;
int a[N];
int tr[N];
int g[N], l[N];

int lowbit(int x)
{
    return x & -x;
}
void add(int x, int c)
{
    for(int i = x; i <= n; i += lowbit(i))
        tr[i] += c;
}
int sum(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    
    for(int i = 1; i <= n; i ++ )
    {
        int y = a[i];
        add(y, 1);
        g[i] = sum(n) - sum(y);//找到比y大的所有数
        l[i] = sum(y - 1); //找到比y小的数
    }
    memset(tr, 0, sizeof tr);
    int ans1 = 0, ans2 = 0;
    for(int i = n; i; i -- )
    {
        int y = a[i];
        add(y, 1);
        ans1 += g[i] * (sum(n) - sum(y));
        ans2 += l[i] * sum(y - 1);
    }
    cout << ans1 << " " << ans2;
}

242. 一个简单的整数问题 - AcWing题库

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int n, m;
int a[N];
int tr[N];
int lowbit(int x)
{
    return x & -x;
}
void add(int x, int c)
{
    for(int i = x; i <= n; i += lowbit(i))
        tr[i] += c;
}
int query(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) 
    {
        cin >> a[i];
        add(i, a[i] - a[i - 1]);
    }
    while (m -- ){
        char t;
        int a, b, c;
        cin >> t;
        if(t == 'Q')
        {
            cin >> a;
            cout << query(a) << endl;
        }
        else
        {
            cin >> a >> b >> c;
            add(a, c);
            add(b + 1, -c);
        }
    }
}

243. 一个简单的整数问题2 - AcWing题库

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
int n, m;
const int N = 100010;
int a[N];
int tr1[N];//b[i]前缀和
int tr2[N];//b[i]*i前缀和
int lowbit(int x)
{
    return  x & -x;
}
void add(int x, int c)
{
    for(int i = x; i <= n; i += lowbit(i))
    {
        tr1[i] += c;
        tr2[i] += x * c;
    }
}
int query(int x)
{
    int res1 = 0, res2 = 0;
    for(int i = x; i; i -= lowbit(i))
    {
        res1 += tr1[i];
        res2 += tr2[i];
    }
    return res1 * (x + 1) - res2;
}
main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        add(i, a[i] - a[i - 1]);
    }
    while (m -- ){
        char t;
        int a, b, c;
        cin >> t;
        if(t == 'Q')
        {
            cin >> a >> b;
            cout << query(b) - query(a - 1) << endl;
        }
        else
        {
            cin >> a >> b >> c;
            add(a, c);
            add(b + 1, -c);
        }
    }
}

244. 谜一样的牛 - AcWing题库

//从剩余的数种，找到第k小的数
//删除某个数

//找到一个最小x的x使得sum(x) = k

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;

const int N = 100100;
int n;
int tr[N], a[N];
int lowbit(int x)
{
    return x & - x;
}
void add(int x, int c)
{
    for(int i = x; i <= n; i += lowbit(i)) 
        tr[i] += c;
}
int sum(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}
int find(int x)
{
    int l = 1, r = n;
    int ans = n;
    while(l <= r)
    {
        int mid = l + r >> 1;
        if(sum(mid) > x)
        {
            r = mid - 1;
        }
        else if(sum(mid) < x)
        {
            l = mid + 1;
        }
        else 
        {
            ans = min(ans, mid);
            r = mid - 1;
        }
    }
    return ans;
}
int main()
{
    cin >> n;
    for(int i = 2; i <= n; i ++ ) cin >> a[i];
    
    for(int i = 1; i <= n; i ++ ) add(i, 1);
    stack<int> st;
    for(int i = n; i; i -- )
    {
        int k = find(a[i] + 1);// 找到最小的k，使得sum(k) = a[i] + 1;
        add(k, -1);
        st.push(k);
    }
    while(st.size())
    {
        cout << st.top() << endl;
        st.pop();
    }
}