Блог пользователя conqueror_of_conqueror

Автор conqueror_of_conqueror, история, 10 лет назад, По-английски

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

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +20 Проголосовать: не нравится
»
10 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится +25 Проголосовать: не нравится

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;
	}