线段树&树状数组

树状数组

树状数组板子 注意在主函数中使用的时候 假设数组为n 需要写为BiTree(n + 1) 因为树状数组范围是1~n

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
typedef long long ll;
class BiTree
{
    int MAXN;
    vector<int>tree;
    ll lowbit(ll x)
    {
        return x & (-x);
    }
public:
    BiTree(int _MAXN = 100010):MAXN(_MAXN)
    {
        tree.resize(MAXN);
    }
    void add(int index, int x)
    {
        for (int i = index; i < MAXN; i+=lowbit(i))
        {
            tree[i] += x;
        }
    }
    ll pre(int n)
    {
        ll sum = 0;
        for (int i = n; i; i -= lowbit(i))
        {
            sum += tree[i];
        }
        return sum;
    }
    // (l, r]
    ll pre(int l, int r)
    {
        return pre(r) - pre(l);
    }
};

307. 区域和检索 - 数组可修改 - 力扣（LeetCode）

树状数组模板题 求不断修改数组的情况下的区间和

主要是add函数 for循环结束条件是i < tree.size()

然后修改了数组元素 要把数组变为val 然后tree里面的值也相应地要修改 修改了delta

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
class NumArray {
private:
    vector<int>nums;
    vector<int>tree;
    int lowbit(int x)
    {
        return x & (-x);
    }
    int pre(int n)
    {
        int sum = 0;
        for (int i = n; i ; i -= lowbit(i))
        {
            sum += tree[i];
        }
        return sum;
    }
public:
    NumArray(vector<int>& nums):nums(nums.size()), tree(nums.size() + 1)
    {
        for (int i = 0; i < nums.size(); i++)
        {
            add(i, nums[i]);
        }
    }
    
    void add(int index, int val) 
    {
        int delta = val - nums[index];
        nums[index] = val;
        for (int i = index + 1; i < tree.size(); i += lowbit(i))
        {
            tree[i] += delta;
        }
    }
    
    int pre(int left, int right) 
    {
        return pre(right + 1) - pre(left);
    }
};

3072. 将元素分配到两个数组中 II - 力扣（LeetCode）

离散化+树状数组

由于数的范围在1e9 太大了 数组开不下 所以要用离散化 为什么可以离散化 因为他只是为了比大小 那把数去重排序后映射到1~n的区间就行了 由于树状数组从1开始 建议映射也从1开始

用unordered_map把每个数映射

树状数组的部分 首先把板子打上

树状数组 存什么呢？ 别的题树状数组（如上题）可能是存前缀和 但是这个题目不一样 他主要是看前面有几个数比他大 我们又已经把数映射了 所以每次add的时候就加1表示index这个地方多了一个数 那么算出来的前缀和就是到1~n这个地方共有几个数 那就是比他小的数的个数 再用size减一下就得到比他大的数的个数

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
typedef long long ll;
class BiTree
{
    int MAXN;
    vector<int>tree;
    ll lowbit(ll x)
    {
        return x & (-x);
    }
public:
    BiTree(int _MAXN = 100010):MAXN(_MAXN)
    {
        tree.resize(MAXN);
    }
    void add(int index, int x)
    {
        for (int i = index; i < MAXN; i+=lowbit(i))
        {
            tree[i] += x;
        }
    }
    ll pre(int n)
    {
        ll sum = 0;
        for (int i = n; i; i -= lowbit(i))
        {
            sum += tree[i];
        }
        return sum;
    }
    // (l, r]
    ll pre(int l, int r)
    {
        return pre(r) - pre(l);
    }
};


class Solution {
public:
    vector<int> resultArray(vector<int>& nums) {
        unordered_map<int, int>mp;
        vector<int>tmp(nums);
        sort(tmp.begin(), tmp.end());
        tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
        int m = tmp.size(), n = nums.size();
        for (int i = 0; i < m; i++)mp[tmp[i]] = i + 1;

        vector<int>a{nums[0]},b{nums[1]};
        BiTree t1(m + 1), t2(m + 1);
        t1.add(mp[nums[0]], 1);
        t2.add(mp[nums[1]], 1);

        for (int i = 2; i < n; i++)
        {
            int x = nums[i];
            int v = mp[nums[i]];
            int gc1 = a.size() - t1.pre(v);
            int gc2 = b.size() - t2.pre(v);

            if (gc1 > gc2 || (gc2 == gc1 && a.size() <= b.size()))
            {
                a.push_back(x);
                t1.add(v, 1);
            }
            else 
            {
                b.push_back(x);
                t2.add(v, 1);
            }
            
        }
        a.insert(a.end(), b.begin(), b.end());
        return a;
    }
};

1265. 数星星 - AcWing题库

主要是要理解树状数组的含义 update函数到底在加什么

像这种计数的题目 而不是求数组区间和 一般就是update(i, 1)表示在i处多了一个什么什么东西

然后还有这个题的细节 求ans[t.pre(x)]++要先求 因为如果先update的话 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
#include <iostream>
#include <vector>
using namespace std;
class BiTree
{
    int MAXN;
    vector<int>tree;
    int lowbit(int x)
    {
        return x &(-x);
    }
public:
    BiTree (int _MAXN = 100010):MAXN(_MAXN)
    {
        tree.resize(MAXN);
    }
    void upd(int index, int x)
    {
        for (int i = index; i <= MAXN; i+=lowbit(i))
        {
            tree[i] += x;
        }
    }
    int pre(int n)
    {
        int sum = 0;
        for (int i = n; i; i -= lowbit(i))
        {
             sum += tree[i];
        }
        return sum;
    }
    int pre(int l, int r)
    {
        return pre(r) - pre(l);
    }
};
int main()
{
    int n;
    cin>>n;
    BiTree t(32001);
    vector<int>ans(n);
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin>>x>>y;
        x ++;
        ans[t.pre(x)]++;
        t.upd(x, 1);
        
    }
    for (int i = 0; i < n; i++)
    {
        cout<<ans[i]<<endl;
    }
}

线段树

下面几道都是板子题 分别代表线段树处理不同的查询

1270. 数列区间最大值 - AcWing题库（add and max）

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 <iostream>
#include <vector>
using namespace std;
const int MAXN = 100005;
typedef long long ll;
ll nums[MAXN], tree[MAXN * 4], mark[MAXN * 4];
ll n, m;
inline void push_down(ll p, ll len)
{
    mark[p * 2] += mark[p];
    mark[p * 2 + 1] += mark[p];
    tree[p * 2] += mark[p * 2] * (len - len / 2);
    tree[p * 2 + 1] += mark[p * 2 + 1] * (len / 2);
    mark[p] = 0;
}
void bulid(ll l = 1, ll r = n, ll p = 1)
{
    if (l == r) 
        tree[p] = nums[l];
    else
    {
        ll mid = l + r >> 1;
        bulid(l, mid, p * 2);
        bulid(mid + 1, r, p * 2 + 1);
        tree[p] = max(tree[p * 2], tree[p * 2 + 1]);
    }
}

ll query(ll l, ll r, ll p=1, ll cl=1, ll cr=n)
{
    if (cl > r || cr < l)
        return 0;
    else if (cl >= l && cr <= r)
    {
        return tree[p];
    }
    else 
    {
        ll mid = cl + cr >> 1;
        push_down(p, cr - cl + 1);
        return max(query(l, r, p * 2, cl, mid), query(l, r, p * 2 + 1, mid + 1, cr));
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &nums[i]);
    }
    bulid();
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin>>a>>b;
        cout<<query(a, b)<<endl;
    }
}

add and sum

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
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 100010;
ll nums[MAXN], tree[MAXN * 4], mark[MAXN * 4], n, m;

void push_down(ll p, ll len)
{
    mark[p * 2] += mark[p];
    mark[p * 2 + 1] += mark[p];
    tree[p * 2] += mark[p] * (len - len / 2);
    tree[p * 2 + 1] += mark[p] * (len / 2);
    mark[p] = 0;
}
void bulid(ll l=1, ll r=n, ll p=1)
{
    if (l == r)
        tree[p] = nums[l];
    else 
    {
        ll mid = l + r >> 1;
        bulid(l, mid, p * 2);
        bulid(mid + 1, r, p * 2 + 1);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }
}
void update(ll l, ll r, ll d, ll p = 1, ll cl = 1, ll cr = n)
{
    if (cl > r || cr < l)
        return;
    else if (cl >= l && cr <= r)
    {
        tree[p] += (cr - cl + 1) * d;
        if (cr > cl)
            mark[p] += d;
    }
    else
    {
        ll mid = l + r >> 1;
        push_down(p, cr - cl + 1);
        update(l, r, d, p, cl, mid);
        update(l, r, d, p, mid + 1, cr);
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }
}
ll query(ll l, ll r, ll p=1, ll cl=1, ll cr=n)
{
    if (cl > r || cr < l)
        return 0;
    else if (cl >= l && cr <= r)
    {
        return tree[p];
    }
    else
    {
        ll mid = l + r >> 1;
        push_down(p, cr - cl + 1);
        return query(l, r, p * 2, cl, mid) + query(l, r, p * 2 + 1, mid + 1, )
    }
}
algorithm
#algorithm #Ans
线段树&树状数组
https://brtulien.github.io/2024/03/07/线段树-树状数组/
作者
Brtulien
发布于
2024年3月7日
更新于
2024年7月1日
许可协议