Algorithm Template

Posted on | In ,

Algorithm Template for Leetcoder user ManuShi98, Codeforces user KihoMaaya and ManuShi.

Interval Query

Fenwick(Binary Index Tree)

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
// Index should start from 1, size should be least 2 larger than real size.
template <typename T>
class fenwick {
private:
    vector<T> fenw;
    int n;
    T lowbit(T x) {
        return ((x)&(-x));
    }
public:
    fenwick(int _n):n(_n) {
        fenw.resize(n);
    }

    void modify(int x, T v) {
        while (x<n) {
            fenw[x]+=v;
            x+=lowbit(x);
        }
    }

    T get(int x) {
        T v = T();
        while(x>0) {
            v += fenw[x];
            x-=lowbit(x);
        }
        return v;
    }
};

Segment Tree with lazy strategy

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
template<class T>
class segmentTreeNode{
public:
    int left, right, length;
    // Values that should be maintain
    T value;
    T lazyValue;
    segmentTreeNode() {
        left = -1, right = -1;
        value = 0;
        lazyValue = 0;
        length = 0;
    }
    bool isValid() {
        return left >= 0 && right >= 0;
    }
};

template<class T>
class segmentTree{
private:
    bool lazyOn;
    bool initReady;
    vector<segmentTreeNode<T> > tree;
    // READ THIS VECTOR AS DATA
    vector<T> nums;
    int lson(int root) {
        return root<<1;
    }
    int rson(int root) {
        return (root<<1)+1;
    }
    // Write code here for push up operation.
    void pushUp(int root) {
        tree[root].value = tree[lson(root)].value+tree[lson(root)].length*tree[lson(root)].lazyValue+tree[rson(root)].value+tree[rson(root)].length*tree[rson(root)].lazyValue;
    }
    // Write code here for lazy tag push down.
    void pushDown(int root) {
        tree[lson(root)].lazyValue+=tree[root].lazyValue;
        tree[rson(root)].lazyValue+=tree[root].lazyValue;
        tree[root].value = tree[root].value + tree[root].length*tree[root].lazyValue;
        tree[root].lazyValue = 0;
    }
public:
    segmentTree() {
        this->lazyOn = false;
        this->initReady = false;
    }
    segmentTree(int size, int left, int right, vector<T> nums, bool lazyOn = false) {
        init(size, left, right, nums, lazyOn);
    }
    void init(int size, int left, int right, vector<T> nums, bool lazyOn = false) {
        tree.resize(size*4);
        this->lazyOn = lazyOn;
        this->initReady = true;
        this->nums = nums;
        build(1, left, right);
    }
    void build(int root, int left, int right) {
        assert(initReady==true);
        tree[root].left = left, tree[root].right = right;
        tree[root].length = right-left+1;
        tree[root].value = 0;
        tree[root].lazyValue = 0;
        if(left == right) {
            // Write code here, base case with interval length 1.
            tree[root].value = nums[left];
        } else {
            int mid = (left+right)>>1;
            build(lson(root), left, mid);
            build(rson(root), mid+1, right);
            pushUp(root);
        }
    }
    void updateInterval(int left, int right, T val) {
        updateInterval(1, left, right, val);
    }
    // interval update with lazy tag;
    void updateInterval(int root, int left, int right, T val) {
        assert(initReady==true);
        if (left<=tree[root].left&&tree[root].right<=right) {
            // Write code here, update logic
            if(lazyOn) {
                tree[root].lazyValue += val;
                return;
            } else {
                if(tree[root].left==tree[root].right) {
                    tree[root].value += val;
                    return;
                }
            }
        }
        if(lazyOn) {
            pushDown(root);
        }
        int mid = (tree[root].left+tree[root].right)>>1;
        if (left<=mid) {
            updateInterval(lson(root), left, right, val);
        }
        if (right>mid) {
            updateInterval(rson(root), left, right, val);   
        }
        pushUp(root);
    }
    void updatePoint(int pos, T val) {
        updatePoint(1, pos, val);
    }
    // point update
    void updatePoint(int root, int pos, T val) {
        assert(initReady == true);
        updateInterval(1, pos, pos, val);
    }
    T query(int left, int right) {
        return query(1, left, right);
    }
    T query(int root, int left, int right) {
        if(left<=tree[root].left&&tree[root].right<=right) {
            return tree[root].value+tree[root].lazyValue*tree[root].length;
        } else {
            if(lazyOn) {
                pushDown(root);
            }
            int mid = (tree[root].left+tree[root].right)>>1;
            T sum = 0;
            if(left<=mid) {
                sum+=query(lson(root), left, right);
            }
            if(right>mid) {
                sum+=query(rson(root), left, right);
            }
            return sum;
        }
    }
    void debug() {
        for(int i=1;i<tree.size();i++) {
            cerr<<"index:"<<i<<endl;
            cerr<<"left:"<<tree[i].left<<endl;
            cerr<<"right:"<<tree[i].right<<endl;
            cerr<<"value:"<<tree[i].value<<endl;
            cerr<<"lazyTag:"<<tree[i].lazyValue<<endl;
        }
    }
};

Graph

Number Theory

Modular

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
102
103
104
105
106
107
108
109
110
111
112
113
114
// This template is based on tourist's template<Modular>
// Used for modular calculation
const long long MOD = 998244353L;
class Mint {
private:
    void extgcd(long long a, long long b, long long& x, long long& y) const{
        if(b==0) {
            x=1, y=0;
            return;
        }
        extgcd(b, a%b, y, x);
        y-=a/b*x;
    }
public:
    long long value;
    Mint() {
        value = 0;
    }
    Mint(const long long &x) {
        value = normalize(x);
    }
    Mint(const Mint &x) {
        value = x.value;
    }
    static long long normalize(const long long &x) {
        long long v = x%MOD;
        if(v<0)v+=MOD;
        return v;
    }
    Mint& operator +=(const Mint& other) {
        if((value+=other.value)>=MOD) {
            value-=MOD;
        }
        return *this;
    }
    Mint& operator -=(const Mint& other) {
        if((value-=other.value)<0) {
            value+=MOD;
        }
        return *this;
    }
    template <typename U>
    Mint& operator +=(const U& other) {
        return *this+=Mint(other);        
    }
    template <typename U>
    Mint& operator -=(const U& other) {
        return *this-=Mint(other);    
    }
    Mint& operator++(){
        return *this+=1;
    }
    Mint& operator--() {
        return *this-=1;
    }
    Mint operator-() const {
        return Mint(-value);
    }
    Mint& operator*= (const Mint& rhs) {
        value = normalize(value*rhs.value);
        return *this;
    }
    template <typename U>
    Mint& operator*= (const U& other) {
        Mint tmp(other);
        value = normalize(value*tmp.value);
        return *this;
    }
    Mint inv() const {
        // value and MOD should be coprime
        assert(gcd(value, MOD)==1);
        long long x, y;
        extgcd(value, MOD, x, y);
        return Mint(x);
    }
    Mint& operator /=(const Mint& other) {
        Mint tmp = other.inv();
        return *this*=tmp;
    }
    bool operator ==(const Mint& other) {
        return value==other.value;
    }
    bool operator !=(const Mint& other) {
        return value!=other.value;
    }
    Mint operator +(const Mint& other) {
        return Mint(value+other.value);
    }
    Mint operator -(const Mint& other) {
        return Mint(value-other.value);
    }
    Mint operator *(const Mint& other) {
        return Mint(value*other.value);
    }
    Mint operator /(const Mint& other) {
        return Mint(Mint(value)*other.inv());
    }
    template<typename T>
    Mint power(const T& b) {
        assert(b>=0);
        Mint x=value, res=1;
        T p = b;
        while(p) {
            if(p&1)res*=x;
            x*=x;
            p>>=1;
        }
        return res;
    }
    string to_string() {
        return to_string(value);
    }
};