conqueror_of_conqueror's blog

0-Indexing a BIT
By conqueror_of_conqueror, history, 8 years ago, In English

Hi, I'm a FiveAtomTree (5-indexed...), and I'm wondering how I can 0-index a BIT easily. I know I can just update upd(index+1, value), but at times it's really inconvenient.

I remember there was a comment on a contest announcement about it, but I forgot it and can't find it...

Anyone wanna hit me up?

Thanks~!

orz

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

http://ideone.com/8k2jMb

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

    Thanks, can you please tell me how it works? Do you implement the normal BIT with i&( - i)? I can't see how i = (i&(i + 1)) - 1 works here.

    Thanks!

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      It has the same structure of tree as with i&( - i), but all indices are shifted by 1, because of such function.

      → Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it +25 Vote: I do not like it

It's very easy to implement a 0-indexed BIT, all you need is to increase pos by 1 in the function add and sum.

        const int MAX_N = 100000;
        int s[MAX_N], n;
	#define lowbit(x) ((x) & -(x))
	inline void add(int pos, int d) {
		for (int i = pos + 1; i <= n; i += lowbit(i))
                        s[i] += d;
	}
	inline int sum(int x) {
		int res = 0;
		for (int i = pos + 1; i > 0; i -= lowbit(i))
                        res += s[i];
		return res;
	}
→ Reply