### rng_50216's blog

By rng_50216, 7 years ago, ,

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

• 0

 » 7 years ago, # |   -13 These operations are not supported by BIT. Use segment tree instead.
•  » » 7 years ago, # ^ | ← Rev. 2 →   -17 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.
 » 7 years ago, # | ← Rev. 5 →   +19 For the second problem:let y[i] = x[i]-x[i-1] let z[i] = y[i] * ifor 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 thatsum(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[]
 » 7 years ago, # |   0 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.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +2 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
 » 7 years ago, # | ← Rev. 3 →   +5 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; } }; 
•  » » 7 years ago, # ^ |   -8 Yes, thanks. I've seen you wrote that in another blog.But I still want to learn, how to do it easily using BIT.
•  » » 5 years ago, # ^ |   0 Could you please explain how this works ? And why do N have to be power of 2 ?
•  » » » 5 years ago, # ^ |   +3 Actually it is segment tree...
•  » » 4 years ago, # ^ |   0 plz explain me how can you sure that po+N be the leaf node if N=1<<17 what happened if i use N=1<<25 it is possible that leaf node can be left or right of pos+Nthen what to do?
•  » » 4 years ago, # ^ |   0 plz explain me how can you sure that po+N be the leaf node if N=1<<17 what happened if i use N=1<<25 it is possible that leaf node can be left or right of pos+N then what to do?
 » 7 years ago, # |   +2 Can you explain what is BIT? Is it binary search tree or Fenwick tree?
•  » » 7 years ago, # ^ |   -11 It's Fenwick Tree.
•  » » 5 years ago, # ^ |   0 Binary indexed tree.
•  » » » 5 years ago, # ^ |   +38
 » 7 years ago, # |   0 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; } 
 » 7 years ago, # | ← Rev. 7 →   -7 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.