Binary-Indexed Tree

From EOJ Wiki
Revision as of 14:38, 10 March 2018 by Ultmaster (talk | contribs) (Created page with "<syntaxhighlight lang='cpp'> template <typename T> class BIT { private: T a[N + 10]; public: void add(int x, T d) { x++; while (x < N) { a...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
template <typename T>
class BIT {
private:
    T a[N + 10];

public:
    void add(int x, T d) {
        x++;
        while (x < N) {
            a[x] += d;
            x += x & -x;
        }
    }
    T query(int x) {
        x++; T ret = 0;
        while (x) {
            ret += a[x];
            x -= x & -x;
        }
        return ret;
    }
    T query_interval(int a, int b) {
        // closed interval
        return query(b) - query(a - 1);
    } 

    /***** The following should be used exclusively *****/
    inline T query2(int x) {
        // used to query some value (not some sum)
        return query(x);
    }
    void add2(int a, int b, T d) {
        add(a, d); add(b + 1, -d);
    }
};