DSA library

a_dsa.md

Fenwick Tree (Binary Indexed Tree)

• https://jamboard.google.com/d/13V-Haxvp1OsPOxmYaQe7ZMj8Oor5lD07fDZCMT8jnXw/viewer?f=10

fenwick.cpp

struct Fenwick {
    int n;
    vector<int> arr;
    vector<int> bit;
    
    Fenwick(int size): n(size) {
        arr = vector<int>(n);
        bit = vector<int>(n);
    }
    
    int qry(int pos) {
        int sum = 0;
        while(pos) {
            sum += bit[pos];
            pos -= pos & (-pos);
        }
        return sum;
    }
    
    void upd(int i, int val) {
        int pos = i;
        while(pos < n) {
            bit[pos] += val - arr[i];
            pos += pos & (-pos);
        }
        arr[i] = val;
    }
};

trie.cpp

struct TrieNode{
    char val;
    bool end;
    map<char, TrieNode*> children;
    
    TrieNode(char c): val(c), end(false) {}
    
    void insert(string word){
        auto temp = this;
        for(char c: word){
            if(!temp->children.count(c)){
                temp->children[c] = new TrieNode(c);
            }
            temp = temp->children[c];
        }
        temp->end = true;
    }
    
    bool match(string word){
        auto temp = this;
        for(char c: word) {
            if(!temp->children.count(c)) {
                if(isupper(c)) return false;
                continue;
            }
            temp = temp->children[c];
        }
        return temp->end;
    }
};