Next Nest

wusa!~(•㉨•)

「轉載】張 正錦 菌給的模板 II 數據結構

发表于 Valine：

第二輯 數據結構

  • 綫段樹
  • 樹狀數組
  • 離散化
  • STL

Segment Tree

C++
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<string.h>
#define nqp main

using namespace std;

const int maxn = 100010;
int A[maxn],n,ans,ans1;

struct hzw
{
    int sum,lc,rc,tag,maxx;
}a[maxn];

void update(int rt)
{
    a[rt].sum = a[a[rt].lc].sum + a[a[rt].rc].sum;
    a[rt].maxx = max(a[a[rt].lc].maxx,a[a[rt].rc].maxx);
}

void pushdown(int l, int r, int rt)
{
    int mid = (l+r) >> 1;
    a[a[rt].lc].sum += (mid-l+1) * a[rt].tag;
    a[a[rt].lc].tag += a[rt].tag;
    a[a[rt].lc].maxx += a[rt].tag;
    a[a[rt].rc].sum += (r-mid) * a[rt].tag;
    a[a[rt].rc].tag += a[rt].tag;
    a[a[rt].rc].maxx += a[rt].tag;
    a[rt].tag = 0;
}

void modify(int l, int r, int rt, int nowl, int nowr, int w)
{
    if(l == nowl && r == nowr)
    {
        a[rt].sum += (r-l+1) * w;
        a[rt].maxx += w;
        a[rt].tag += w;
        return;
    }
    int mid = (l+r) >> 1;
    pushdown(l,r,rt);
    if(nowr <= mid) modify(l,mid,a[rt].lc,nowl,nowr,w);
    else if(nowl > mid) modify(mid+1,r,a[rt].rc,nowl,nowr,w);
    else
    {
        modify(l,mid,a[rt].lc,nowl,mid,w);
        modify(mid+1,r,a[rt].rc,mid+1,nowr,w);
    }
    update(rt);
}

void query(int l, int r, int rt, int nowl, int nowr)
{
    if(l == nowl && r == nowr)
    {
        ans += a[rt].sum;
        ans1 = max(a[rt].maxx,ans1);
        return;
    }
    int mid = (l+r) >> 1;
    pushdown(l,r,rt);
    if(nowr <= mid) query(l,mid,a[rt].lc,nowl,nowr);
    else if(nowl > mid) query(mid+1,r,a[rt].rc,nowl,nowr);
    else
    {
        query(l,mid,a[rt].lc,nowl,mid);
        query(mid+1,r,a[rt].rc,mid+1,nowr);
    }
}

int tot = 1;
void build(int l, int r, int rt)
{
    if(l == r)
    {
        a[rt].sum = A[l];
        a[rt].maxx = A[l];
        return;
    }
    int mid = (l+r) >> 1;
    a[rt].lc = ++tot;
    build(l,mid,a[rt].lc);
    a[rt].rc = ++ tot;
    build(mid+1,r,a[rt].rc);
    update(rt);
}

int nqp()
{
    cin >> n;
    for(int i=1; i<=n; i++) cin >> A[i];
    build(1,n,1);
    query(1,n,1,1,n);
    cout << ans << ' '<< ans1;
    return 0;
}

Fenwick Array

C++
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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<queue>

using namespace std;

const int maxn = 500050;
int tree[maxn],m,n;

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

void add(int x, int k)//维护 ,修改 
{
    while(x<=n)
    {
        tree[x] += k;
        x += lowbit(x);
    }
}

int query(int x)//前缀和查询 
{
    int ans = 0;
    while(x!=0)
    {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int a;
        scanf("%d",&a);
        add(i,a);
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a==1)
            add(b,c);
        if(a==2)
            cout<<query(c)-query(b-1)<<endl;
    }
    return 0;
}

Discretization

Hzw版离散化

C++
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
#include<iostream>
#include<algorithm>
#include<string.h>
#include<cstdio>
#include<queue>
#define nqp main

using namespace std;

int const maxn=1e5+10;
int a[maxn], t[maxn];
int n;

int nqp()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]),t[i]=a[i];
    sort(t+1,t+n+1);
    int m=unique(t+1,t+1+n)-t-1
    for(int i=1; i<=n; i++)
        a[i]=lower_bound(t+1,t+1+m,a[i])-t;
    for(int i=1; i<=n; i++)
    {
        cout << a[i] << ' ';
    } 
    return 0;
}

STL (Standard Template Library)

queue

先進先出的綫性數據結構。

  • Definition

    C++
    1
    2
    3
    4
    template <
        class T,
        class Container = std::deque<T>
    > class queue;

  • Members

    • .push(T _element) 向隊列中壓入元素
    • .pop() 彈出隊尾元素
    • .empty() 查詢隊列是否爲空
    • .size() 查詢隊列大小
    • .front() 返回隊首元素
    • .back() 返回隊尾元素

stack

先進後出的綫性數據結構。

  • Definition

    C++
    1
    2
    3
    4
    template <
        class T,
        class Container = std::deque<T>
    > class stack;

  • Members

    • .push(T _element) 向棧中壓入元素
    • .pop() 彈出棧頂元素
    • .top() 獲取棧頂元素
    • .empty() 審察棧中是否爲空
    • .size() 審查棧中元素數目

vector

不定长数组

  • Definition

    C++
    1
    2
    3
    4
    template <
        class T,
        class Allocator = std::allocator<T>
    > class vector;

  • Iterator

    • Definition

      C++
      1
      vector <T> :: iterator _iter;

    • Usage

      C++
      1
      2
      3
      4
      5
      6
      *_iter; // 取值
      ++_iter; // 向下一位移動
      --_iter; // 向上一位移動
      // 裝逼上天ノ練一：循環讀出矢量中的元素
      for (vector <int> :: iterator _iter = vec.begin(); _iter != vec.end(); ++_iter)
          printf("%d, ", *_iter);

  • Members

    • .push_back(T _element) 在最後添加元素
    • .size() 審查矢量的元素數目
    • .clear() 清空矢量
    • .begin() 返回指向第一個元素的迭代器
    • .end() 返回指向最後一個元素之後一位的迭代器
    • .insert(vector <T> :: iterator _iter, T _element) 在迭代器指向位置前插入元素

set

集合

  • Definition

    C++
    1
    2
    3
    4
    5
    template <
        class T,                    // set::key_type/value_type
        class Compare = less <T>,   // set::key_compare/value_compare
        class Alloc = allocator <T> // set::allocator_type
        > class set;

  • Members

    • .insert(T _element) 向集合中插入元素
    • .erase(T _element) 從集合中刪除指定值的元素
    • .clear() 清空集合
    • .count(T _element) 清點集合中指定值的元素的數目
    • .lower_bound(T _element) 返回指向第一個>=指定值的元素的迭代器
    • .upper_bound(T _element) 返回指向第一個>指定值的元素的迭代器
    • .equal_range(T _element) 返回一個 pair(.lower_bound(T _element), .upper_bound(T _element))

map

映射

  • Definition

    C++
    1
    2
    3
    4
    5
    6
    template <
        class Key,                                          // map::key_type
        class T,                                            // map::mapped_type
        class Compare = std::less <Key>,                    // map::key_compare
        class Alloc = std::allocator <pair <const Key, T> > // map::allocator_type
    > class map;

  • Notes

    • 超过40w最好别用, 时间复杂度会变成O(log N)