rng_50216's blog

By rng_50216, 11 years ago, In English

Does anyone have implementation of BIT for following operations:

setmin(i, x) = a[i] := min(a[i], x)

getmin(l, r) = min(a[x], l <= x <= r)

Does anyone have implementation of BIT for following operations:

add(l, r, x) = a[i] += x, where l <= i <= r

getsum(l, r) = sum(a[i]), where l <= i <= r

Tags bit
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
  Vote: I like it -13 Vote: I do not like it

These operations are not supported by BIT. Use segment tree instead.

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it -17 Vote: I do not like it

    Let's wait for more experienced coders.

    There are the ways, that use more memory and time for doing that operations using BIT, but it's still faster than using segment tree.

»
11 years ago, # |
Rev. 5   Vote: I like it +19 Vote: I do not like it

For the second problem:

let y[i] = x[i]-x[i-1] let z[i] = y[i] * i

for example sum(1..3) x[i] = x[1] + x[2] + x[3] x[1] = x[1] x[2] = y[2] + y[1]; x[3] = y[3] + y[2] + y[1]

so x[1]+x[2]+x[3] = 4(y[1]+y[2]+y[3])-1*x[1]-2 * x[2]-3 * x[3] = 4 * (y[1] + y[2] + y[3])-(z[1] + z[2] + z[3])

we can infer that

sum(1..n) x[i] = sum(1..n) n * y[i]-sum(1..n) i * y[i] = sum(1..n) n * y[i]-sum(1..n) z[i]

notice that each modification can modify at most two elements of y[] and z[] so we can use two BITs to maintain y[] and z[]

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For the first problem:

if l is always the first element of a[], then the normal BIT can support these operations easily. but I can't come up with ideas when l can be other element.

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    It won't do. Once you try to increase element, there is no reliable way to determine the new value for all intervals, which contain it. You can only decrease elements in this case.

    Upd. Sorry, didn't notice min(a[i],x) in topic

»
11 years ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

for the first one there is easy to remember short code

const int N = 1 << 17; // has to be power of 2
const int inf = 1 << 28;

struct RMQ {
    int a[N * 2];
    RMQ() {
        FOR(i, N * 2)
            a[i] = inf;
    }
    void SetMin(int pos, int x) {
        for (int i = pos + N; i; i >>= 1)
            a[i] = min(a[i], x);
    }
    int GetMin(int L, int R) const // [L, R) i.e. L <= i < R
    {
        int res = inf;
        for (L += N, R += N; L < R; L >>= 1, R >>= 1) {
            if (L & 1) {
                res = min(res, a[L]);
                L++;
            }
            if (R & 1) {
                R--;
                res = min(res, a[R]);
            }
        }
        return res;
    }
};
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Yes, thanks. I've seen you wrote that in another blog.

    But I still want to learn, how to do it easily using BIT.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain how this works ? And why do N have to be power of 2 ?

»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can you explain what is BIT? Is it binary search tree or Fenwick tree?

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For the second problem I found this very short implementation some time ago, but I didn't analyze it.

typedef long long int lld;
const int MaxN = 1 << 18;


int N;
lld BIT[MaxN][2];

inline void Update ( int idx, lld Value )
{
    for ( int i = idx; i <= N; i += i & -i )
    {
        BIT[i][0] += ( i - idx + 1LL ) * Value;
        BIT[i][1] += Value;
    }
}

inline lld Query ( int idx )
{
    lld Ret = BIT[idx][0];
    for ( int i = idx - ( idx & -idx ); i; i -= i & -i ) Ret += BIT[i][0] + ( idx - i ) * BIT[i][1];
    return Ret;
}
»
11 years ago, # |
Rev. 7   Vote: I like it -7 Vote: I do not like it

For the first problem:

Obviously, setmin(i, x) can be rewritten as setvalue(i, x) if x < a[i], or otherwise ignore the operation. setvalue(i, x) = a[i] := x.

Next, I keep 2 arrays T and a. a is the current array, while T is my Fenwick tree. But instead of keeping minimal value of a range in the Fenwick, I keep index of that value in the a array.

define bit(i) (i & -i)

int que( int l, int r ) { //returns the index of the minimal value in a

int m = 0;
 while( l <= r )
    if( r-bit(r)+1 >= l ) //the interval is fully contained into [l, r]
    {
        if(a[m] < a[ T[r] ]) m = T[r];
        r -=bit(r);
    }
    else
    {
        if(a[m] < a[r]) m = r; //I can't use the fenwick information, so I have to process a single //element
        r--; 
    }
return m;

}

void upd( int x, int val ) {

int y, z;
a[x] = val;
for(y = x; x <= N; x += bit(x)) //y is index of updated element, x is the current fenwick.
    if(T[x] == y) //this should be used for general update cases, for setmin operations it's //useless. About setmin, I'll always be sure that if last value was the best for range, then new //value will also be the good one for range, since the new one is smaller then the last one.
    { //from here I suppose the updated value is greater than last one. 
        z = que(x-bit(x) + 1, x-1); //this takes O(logN) time
        T[x] = (a[z] > a[x]) ? z : x; //the minimal value from the range [x - bit(x) + 1, x] is //minimal between x and [x - bit(x) + 1, x - 1].
    }
    else //just check and update like in normal fenwick version.
    if(a[ T[x] ] < a[ y ])T[x] = y;

}

Both operations run in O(log^2) time worst case. However, execution time for big inputs is comparable with times of segment trees.