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

0-Indexing a BIT
Автор conqueror_of_conqueror, история, 8 лет назад, По-английски

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
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

http://ideone.com/8k2jMb

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
»
8 лет назад, # |
← 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;
	}
→ Ответить