conqueror_of_conqueror's blog

0-Indexing a BIT
By conqueror_of_conqueror, history, 10 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

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

http://ideone.com/8k2jMb

→ Reply
»
10 years ago, hide # |
← 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