Difference between revisions of "Binary-Indexed Tree"

From EOJ Wiki
Jump to navigation Jump to search
(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...")
 
 
(2 intermediate revisions by 2 users not shown)
Line 3: Line 3:
 
class BIT {
 
class BIT {
 
private:
 
private:
     T a[N + 10];
+
    static const int MAXN = N + 100;
 +
     T a[MAXN];
  
 
public:
 
public:
 
     void add(int x, T d) {
 
     void add(int x, T d) {
 
         x++;
 
         x++;
         while (x < N) {
+
         while (x < MAXN) {
 
             a[x] += d;
 
             a[x] += d;
 
             x += x & -x;
 
             x += x & -x;
Line 24: Line 25:
 
         // closed interval
 
         // closed interval
 
         return query(b) - query(a - 1);
 
         return query(b) - query(a - 1);
     }  
+
    }
 +
    int lower_bound(T x) {
 +
        int ret = 0; T cnt = 0;
 +
        int MAX = int(ceil(log(MAXN) / log(2)));
 +
        for (int i = MAX; i >= 0; --i) {
 +
            ret += 1 << i;
 +
            if (ret > N || cnt + a[ret] >= x)
 +
                ret -= 1 << i;
 +
            else cnt += a[ret];
 +
        }
 +
        if (ret >= N) return INF;
 +
        return max(ret, 1);
 +
     }
  
 
     /***** The following should be used exclusively *****/
 
     /***** The following should be used exclusively *****/
Line 35: Line 48:
 
     }
 
     }
 
};
 
};
 +
</syntaxhighlight>
 +
 +
<syntaxhighlight lang='cpp'>
 +
namespace bit {
 +
    using T = LL;
 +
    const int M = -1;
 +
    T c[M];
 +
    inline int lowbit(int x) { return x & -x; }
 +
    void add(int p, T v) {
 +
        for (int i = p + 1; i < M; i += lowbit(i))
 +
            c[i] += v;
 +
    }
 +
    T sum(int p) {
 +
        T ret = 0;
 +
        for (int i = p + 1; i > 0; i -= lowbit(i))
 +
            ret += c[i];
 +
        return ret;
 +
    }
 +
    int kth(T k) {
 +
        int ret = 0;
 +
        T cnt = 0;
 +
        FORD (i, 20, -1) {
 +
            ret += 1 << i;
 +
            if (ret >= M || cnt + c[ret] >= k)
 +
                ret -= 1 << i;
 +
            else cnt += c[ret];
 +
        }
 +
        return ret + 1;
 +
    }
 +
}
 
</syntaxhighlight>
 
</syntaxhighlight>

Latest revision as of 02:52, 19 March 2018

template <typename T>
class BIT {
private:
    static const int MAXN = N + 100;
    T a[MAXN];

public:
    void add(int x, T d) {
        x++;
        while (x < MAXN) {
            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);
    }
    int lower_bound(T x) {
        int ret = 0; T cnt = 0;
        int MAX = int(ceil(log(MAXN) / log(2)));
        for (int i = MAX; i >= 0; --i) {
            ret += 1 << i;
            if (ret > N || cnt + a[ret] >= x)
                ret -= 1 << i;
            else cnt += a[ret];
        }
        if (ret >= N) return INF;
        return max(ret, 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);
    }
};
namespace bit {
    using T = LL;
    const int M = -1;
    T c[M];
    inline int lowbit(int x) { return x & -x; }
    void add(int p, T v) {
        for (int i = p + 1; i < M; i += lowbit(i))
            c[i] += v;
    }
    T sum(int p) {
        T ret = 0;
        for (int i = p + 1; i > 0; i -= lowbit(i))
            ret += c[i];
        return ret;
    }
    int kth(T k) {
        int ret = 0;
        T cnt = 0;
        FORD (i, 20, -1) {
            ret += 1 << i;
            if (ret >= M || cnt + c[ret] >= k)
                ret -= 1 << i;
            else cnt += c[ret];
        }
        return ret + 1;
    }
}