Updating partial sums with Fenwick tree - Revision history

Mio: hardly material change in the for statement

2010-12-28T02:37:07Z

hardly material change in the for statement

← Older revision		Revision as of 19:37, 27 December 2010
Line 30:		Line 30:
	// add val to the k-th element		// add val to the k-th element
	void add(int k, int val) {		void add(int k, int val) {
	for (int i=k~~; i<int(~~v_.size()); i += -i&i)		for (int i=k, e=v_.size(); i<e; i += -i&i)
	v_[i] += val;		v_[i] += val;
	}		}

Mio at 00:19, 2 February 2010

2010-02-02T00:19:45Z

← Older revision		Revision as of 17:19, 1 February 2010
Line 3:		Line 3:
	The idea is to have two actions on positive integers, say <math>A</math> and <math>B</math>, which satisfy the following:		The idea is to have two actions on positive integers, say <math>A</math> and <math>B</math>, which satisfy the following:

	'''Property 1''' ~~Orbit~~ of <math>x</math> under action of <math>A</math>, and orbit of <math>y</math> under action of <math>B</math> intersect in exactly one point if <math>x \leq y</math>, and nowhere otherwise.		'''Property 1''' For any two positive integers <math>x</math> and <math>y</math>, orbit of <math>x</math> under action of <math>A</math>, and orbit of <math>y</math> under action of <math>B</math> intersect in exactly one point if <math>x \leq y</math>, and nowhere otherwise.

	The general algorithm when we have <math>A</math> and <math>B</math> that satisfy the property above is as follows. We will maintain an array of size <math>N</math> with all elements initialized to 0. By updating something we mean adding a quantity to it, whether positive or negative. On each update of the <math>i^{th}</math> sequence element, update all the elements of the array with indices in the <math>A</math> orbit of <math>i</math> by that same amount. To retrieve the partial sum of elements <math>1</math> thru <math>j</math>, sum up all the elements from the array with indices in the <math>B</math> orbit of <math>j</math>.		The general algorithm when we have <math>A</math> and <math>B</math> that satisfy the property above is as follows. We will maintain an array of size <math>N</math> with all elements initialized to 0. By updating something we mean adding a quantity to it, whether positive or negative. On each update of the <math>i^{th}</math> sequence element, update all the elements of the array with indices in the <math>A</math> orbit of <math>i</math> by that same amount. To retrieve the partial sum of elements <math>1</math> thru <math>j</math>, sum up all the elements from the array with indices in the <math>B</math> orbit of <math>j</math>.

Mio at 00:15, 2 February 2010

2010-02-02T00:15:56Z

← Older revision		Revision as of 17:15, 1 February 2010
Line 11:		Line 11:
	Here's the punchline: for a positive integer <math>n</math>, if we call <math>r(n)</math> the integer we get when we isolate the rightmost, i.e. the least significant, set bit in the binary representation of <math>n</math> (so e.g. <math>r(6) = 2</math> and <math>r(8) = 8</math>), then <math>A(i) = i + r(i)</math> and <math>B(i) = i - r(i)</math> satisfy Property 1.		Here's the punchline: for a positive integer <math>n</math>, if we call <math>r(n)</math> the integer we get when we isolate the rightmost, i.e. the least significant, set bit in the binary representation of <math>n</math> (so e.g. <math>r(6) = 2</math> and <math>r(8) = 8</math>), then <math>A(i) = i + r(i)</math> and <math>B(i) = i - r(i)</math> satisfy Property 1.

	Proof: <math>A</math> increases its argument while <math>B</math> decreases it, so if <math>x=y</math> then <math>A^0(x) = B^0(y)</math>, and that's the only intersection. If <math>x < y</math>, then binary representations of <math>x</math> and <math>y</math> are <math>y = a1b_y</math> and <math>x = a0b_x</math> where <math>a</math>, <math>b_x</math>, <math>b_y</math> are (possibly empty) binary sequences, and <math>b_x</math> and <math>b_y</math> are of same length <math>\|b\|</math>. We may have had to pad the representation of <math>x</math> by zeros to the left as needed for this. The action <math>B</math> unsets the rightmost set bit, so eventually <math>y</math> will under action of <math>B</math> arrive at <math>a10^{\|b\|}</math>, if it's not of that form to begin with. If <math>b_x</math> has no set bits, then one more action of <math>B</math> on <math>y</math> will make it equal to <math>x</math>. If <math>b_x</math> has set bits, then <math>A</math>, which turns a number of the form <math>z01^{m}0^{n}</math> into <math>z10^{m+n}</math> will eventually bring <math>x</math> to <math>a10^{\|b\|}</math>, which is where we left <math>y</math>. By the argument from the beginning, this is the only place the two orbits intersect. QED		Proof: <math>A</math> increases its argument while <math>B</math> decreases it, so if <math>x=y</math> then <math>A^0(x) = B^0(y)</math>, and that's the only intersection. If <math>0 < x < y</math>, then binary representations of <math>x</math> and <math>y</math> are <math>y = a1b_y</math> and <math>x = a0b_x</math> where <math>a</math>, <math>b_x</math>, <math>b_y</math> are (possibly empty) binary sequences, and <math>b_x</math> and <math>b_y</math> are of same length <math>\|b\|</math>. We may have had to pad the representation of <math>x</math> by zeros to the left as needed for this. The action <math>B</math> unsets the rightmost set bit, so eventually <math>y</math> will under action of <math>B</math> arrive at <math>a10^{\|b\|}</math>, if it's not of that form to begin with. If <math>b_x</math> has no set bits, then one more action of <math>B</math> on <math>y</math> will make it equal to <math>x</math>. If <math>b_x</math> has set bits, then <math>A</math>, which turns a number of the form <math>z01^{m}0^{n}</math> into <math>z10^{m+n}</math> will eventually bring <math>x</math> to <math>a10^{\|b\|}</math>, which is where we left <math>y</math>. By the argument from the beginning, this is the only place the two orbits intersect. QED

	What's more, in C and its ilk, <math>r(i)</math> is coded as <code>(-i)&i</code>. (Actually, <code>-i&i</code> will parse just fine since unary minus has higher precedence in C than bitwise and.)		What's more, in C and its ilk, <math>r(i)</math> is coded as <code>(-i)&i</code>. (Actually, <code>-i&i</code> will parse just fine since unary minus has higher precedence in C than bitwise and.)

Mio at 19:47, 1 February 2010

2010-02-01T19:47:45Z

← Older revision		Revision as of 12:47, 1 February 2010
Line 13:		Line 13:
	Proof: <math>A</math> increases its argument while <math>B</math> decreases it, so if <math>x=y</math> then <math>A^0(x) = B^0(y)</math>, and that's the only intersection. If <math>x < y</math>, then binary representations of <math>x</math> and <math>y</math> are <math>y = a1b_y</math> and <math>x = a0b_x</math> where <math>a</math>, <math>b_x</math>, <math>b_y</math> are (possibly empty) binary sequences, and <math>b_x</math> and <math>b_y</math> are of same length <math>\|b\|</math>. We may have had to pad the representation of <math>x</math> by zeros to the left as needed for this. The action <math>B</math> unsets the rightmost set bit, so eventually <math>y</math> will under action of <math>B</math> arrive at <math>a10^{\|b\|}</math>, if it's not of that form to begin with. If <math>b_x</math> has no set bits, then one more action of <math>B</math> on <math>y</math> will make it equal to <math>x</math>. If <math>b_x</math> has set bits, then <math>A</math>, which turns a number of the form <math>z01^{m}0^{n}</math> into <math>z10^{m+n}</math> will eventually bring <math>x</math> to <math>a10^{\|b\|}</math>, which is where we left <math>y</math>. By the argument from the beginning, this is the only place the two orbits intersect. QED		Proof: <math>A</math> increases its argument while <math>B</math> decreases it, so if <math>x=y</math> then <math>A^0(x) = B^0(y)</math>, and that's the only intersection. If <math>x < y</math>, then binary representations of <math>x</math> and <math>y</math> are <math>y = a1b_y</math> and <math>x = a0b_x</math> where <math>a</math>, <math>b_x</math>, <math>b_y</math> are (possibly empty) binary sequences, and <math>b_x</math> and <math>b_y</math> are of same length <math>\|b\|</math>. We may have had to pad the representation of <math>x</math> by zeros to the left as needed for this. The action <math>B</math> unsets the rightmost set bit, so eventually <math>y</math> will under action of <math>B</math> arrive at <math>a10^{\|b\|}</math>, if it's not of that form to begin with. If <math>b_x</math> has no set bits, then one more action of <math>B</math> on <math>y</math> will make it equal to <math>x</math>. If <math>b_x</math> has set bits, then <math>A</math>, which turns a number of the form <math>z01^{m}0^{n}</math> into <math>z10^{m+n}</math> will eventually bring <math>x</math> to <math>a10^{\|b\|}</math>, which is where we left <math>y</math>. By the argument from the beginning, this is the only place the two orbits intersect. QED

	What's more, in C and its ilk, <math>r(i)</math> is coded as <code>(-i)&i</code>. (Actually, <code>-i&i</code> will parse just fine since unary minus has higher precedence in C than ~~binary~~ and.)		What's more, in C and its ilk, <math>r(i)</math> is coded as <code>(-i)&i</code>. (Actually, <code>-i&i</code> will parse just fine since unary minus has higher precedence in C than bitwise and.)

	Here's a simple implementation in C++, add error checking as needed		Here's a simple implementation in C++, add error checking as needed

Mio at 10:35, 1 February 2010

2010-02-01T10:35:41Z

← Older revision		Revision as of 03:35, 1 February 2010
Line 1:		Line 1:
	The two straightforward ways to code updating and retrieval of partial sums of sequences are: (a) maintain the array of sequence elements - on each update of a sequence element update just the sequence element, and each time you need a partial sum you compute it from scratch, (b) maintain the array of partial sums - on each update of a sequence element update all the partial sums this element contributes to. In the case (a) update takes <math>O(1)</math> time and retrieval takes <math>O(N)</math>, in the case (b) update takes <math>O(N)</math> and retrieval <math>O(1)</math> time. <math>N</math> is the length of the sequence. The [http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf Fenwick tree] data structure has both update and retrieval taking <math>O(\log N)</math> time in the worst case, while still using the same <math>O(N)</math> amount of space.		The two straightforward ways to code updating and retrieval of partial sums of sequences are: (a) maintain the array of sequence elements - on each update of a sequence element update just the sequence element, and each time you need a partial sum you compute it from scratch, (b) maintain the array of partial sums - on each update of a sequence element update all the partial sums this element contributes to. In the case (a) update takes <math>O(1)</math> time and retrieval takes <math>O(N)</math>, in the case (b) update takes <math>O(N)</math> and retrieval <math>O(1)</math> time, where <math>N</math> is the length of the sequence. The [http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf Fenwick tree] data structure has both update and retrieval taking <math>O(\log N)</math> time in the worst case, while still using the same <math>O(N)</math> amount of space.

	The idea is to have two actions on positive integers, say <math>A</math> and <math>B</math>, so that orbit of <math>x</math> under action of <math>A</math>, and orbit of <math>y</math> under action of <math>B</math> intersect in exactly one point if <math>x \leq y</math>, and none otherwise. We will maintain an array of size <math>N</math> with all elements initialized to 0. On each update of a sequence element <math>i</math>, update all the elements of the array with indices in the <math>A</math> orbit of <math>i</math> by that same amount. To retrieve the partial sum of elements <math>1</math> thru <math>j</math>, sum up all the elements from the array with indices in the <math>B</math> orbit of <math>j</math>. In the case (a) above <math>A</math> is identity and <math>B(j) = j-1</math>, for (b) it's <math>A(i) = i+1</math> and <math>B</math> is the identity.		The idea is to have two actions on positive integers, say <math>A</math> and <math>B</math>, which satisfy the following:

	Here's the punchline: for a positive integer <math>n</math>, if we call <math>r(n)</math> the integer we get when we isolate the rightmost, i.e. the least significant, set bit in the binary representation of <math>n</math> (so e.g. <math>r(6) = 2</math> and <math>r(8) = 8</math>), then <math>A(i) = i + r(i)</math> and <math>B(i) = i - r(i)</math> ~~are two such actions. What's more, in C and its ilk, <math>r(i)</math> is coded as <code>(-i)&i</code>~~.		'''Property 1''' Orbit of <math>x</math> under action of <math>A</math>, and orbit of <math>y</math> under action of <math>B</math> intersect in exactly one point if <math>x \leq y</math>, and nowhere otherwise.

			The general algorithm when we have <math>A</math> and <math>B</math> that satisfy the property above is as follows. We will maintain an array of size <math>N</math> with all elements initialized to 0. By updating something we mean adding a quantity to it, whether positive or negative. On each update of the <math>i^{th}</math> sequence element, update all the elements of the array with indices in the <math>A</math> orbit of <math>i</math> by that same amount. To retrieve the partial sum of elements <math>1</math> thru <math>j</math>, sum up all the elements from the array with indices in the <math>B</math> orbit of <math>j</math>.

			The two straightforward algorithms we discussed in the first paragraph already fit into this scheme. In the case (a) above, <math>A</math> is identity and <math>B(j) = j-1</math>, for (b) it's <math>A(i) = i+1</math> and <math>B</math> is the identity. It's obvious that in both cases the pair <math>A</math> and <math>B</math> satisfy Property 1.

			Here's the punchline: for a positive integer <math>n</math>, if we call <math>r(n)</math> the integer we get when we isolate the rightmost, i.e. the least significant, set bit in the binary representation of <math>n</math> (so e.g. <math>r(6) = 2</math> and <math>r(8) = 8</math>), then <math>A(i) = i + r(i)</math> and <math>B(i) = i - r(i)</math> satisfy Property 1.

	Proof: <math>A</math> increases its argument while <math>B</math> decreases it, so if <math>x=y</math> then <math>A^0(x) = B^0(y)</math>, and that's the only intersection. If <math>x < y</math>, then binary representations of <math>x</math> and <math>y</math> are <math>y = a1b_y</math> and <math>x = a0b_x</math> where <math>a</math>, <math>b_x</math>, <math>b_y</math> are (possibly empty) binary sequences, and <math>b_x</math> and <math>b_y</math> are of same length <math>\|b\|</math>. We may have had to pad the representation of <math>x</math> by zeros to the left as needed for this. The action <math>B</math> unsets the rightmost set bit, so eventually <math>y</math> will under action of <math>B</math> arrive at <math>a10^{\|b\|}</math>, if it's not of that form to begin with. If <math>b_x</math> has no set bits, then one more action of <math>B</math> on <math>y</math> will make it equal to <math>x</math>. If <math>b_x</math> has set bits, then <math>A</math>, which turns a number of the form <math>z01^{m}0^{n}</math> into <math>z10^{m+n}</math> will eventually bring <math>x</math> to <math>a10^{\|b\|}</math>, which is where we left <math>y</math>. By the argument from the beginning, this is the only place the two orbits intersect. QED		Proof: <math>A</math> increases its argument while <math>B</math> decreases it, so if <math>x=y</math> then <math>A^0(x) = B^0(y)</math>, and that's the only intersection. If <math>x < y</math>, then binary representations of <math>x</math> and <math>y</math> are <math>y = a1b_y</math> and <math>x = a0b_x</math> where <math>a</math>, <math>b_x</math>, <math>b_y</math> are (possibly empty) binary sequences, and <math>b_x</math> and <math>b_y</math> are of same length <math>\|b\|</math>. We may have had to pad the representation of <math>x</math> by zeros to the left as needed for this. The action <math>B</math> unsets the rightmost set bit, so eventually <math>y</math> will under action of <math>B</math> arrive at <math>a10^{\|b\|}</math>, if it's not of that form to begin with. If <math>b_x</math> has no set bits, then one more action of <math>B</math> on <math>y</math> will make it equal to <math>x</math>. If <math>b_x</math> has set bits, then <math>A</math>, which turns a number of the form <math>z01^{m}0^{n}</math> into <math>z10^{m+n}</math> will eventually bring <math>x</math> to <math>a10^{\|b\|}</math>, which is where we left <math>y</math>. By the argument from the beginning, this is the only place the two orbits intersect. QED

			What's more, in C and its ilk, <math>r(i)</math> is coded as <code>(-i)&i</code>. (Actually, <code>-i&i</code> will parse just fine since unary minus has higher precedence in C than binary and.)

	Here's a simple implementation in C++, add error checking as needed		Here's a simple implementation in C++, add error checking as needed
Line 22:		Line 30:
	// add val to the k-th element		// add val to the k-th element
	void add(int k, int val) {		void add(int k, int val) {
	for (int i=k; i<int(v_.size()); i += (-i&i))		for (int i=k; i<int(v_.size()); i += -i&i)
	v_[i] += val;		v_[i] += val;
	}		}
Line 29:		Line 37:
	int get(int k) const {		int get(int k) const {
	int r=0;		int r=0;
	for (int i=k; i>0; i -= (-i&i))		for (int i=k; i>0; i -= -i&i)
	r += v_[i];		r += v_[i];
	return r;		return r;

Mio at 06:28, 28 January 2010

2010-01-28T06:28:04Z

← Older revision		Revision as of 23:28, 27 January 2010
Line 1:		Line 1:
	The two straightforward ways to code updating and retrieval of partial sums of sequences are: (a) maintain the array of sequence elements - on each update of a sequence element update just the sequence element, and each time you need a partial sum you compute it from scratch, (b) maintain the array of partial sums - on each update of a sequence element update all the partial sums this element contributes to. In the case (a) update takes <math>O(1)</math> time and retrieval takes <math>O(N)</math>, in the case (b) update takes <math>O(N)</math> and retrieval <math>O(1)</math> time. <math>N</math> is the length of the sequence. The [http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf Fenwick tree] data structure ~~(although it's not really a tree)~~ has both update and retrieval taking <math>O(\log N)</math> time in the worst case, while still using the same <math>O(N)</math> amount of space.		The two straightforward ways to code updating and retrieval of partial sums of sequences are: (a) maintain the array of sequence elements - on each update of a sequence element update just the sequence element, and each time you need a partial sum you compute it from scratch, (b) maintain the array of partial sums - on each update of a sequence element update all the partial sums this element contributes to. In the case (a) update takes <math>O(1)</math> time and retrieval takes <math>O(N)</math>, in the case (b) update takes <math>O(N)</math> and retrieval <math>O(1)</math> time. <math>N</math> is the length of the sequence. The [http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf Fenwick tree] data structure has both update and retrieval taking <math>O(\log N)</math> time in the worst case, while still using the same <math>O(N)</math> amount of space.

	The idea is to have two actions on positive integers, say <math>A</math> and <math>B</math>, so that orbit of <math>x</math> under action of <math>A</math>, and orbit of <math>y</math> under action of <math>B</math> intersect in exactly one point if <math>x \leq y</math>, and none otherwise. We will maintain an array of size <math>N</math> with all elements initialized to 0. On each update of a sequence element <math>i</math>, update all the elements of the array with indices in the <math>A</math> orbit of <math>i</math> by that same amount. To retrieve the partial sum of elements <math>1</math> thru <math>j</math>, sum up all the elements from the array with indices in the <math>B</math> orbit of <math>j</math>. In the case (a) above <math>A</math> is identity and <math>B(j) = j-1</math>, for (b) it's <math>A(i) = i+1</math> and <math>B</math> is the identity.		The idea is to have two actions on positive integers, say <math>A</math> and <math>B</math>, so that orbit of <math>x</math> under action of <math>A</math>, and orbit of <math>y</math> under action of <math>B</math> intersect in exactly one point if <math>x \leq y</math>, and none otherwise. We will maintain an array of size <math>N</math> with all elements initialized to 0. On each update of a sequence element <math>i</math>, update all the elements of the array with indices in the <math>A</math> orbit of <math>i</math> by that same amount. To retrieve the partial sum of elements <math>1</math> thru <math>j</math>, sum up all the elements from the array with indices in the <math>B</math> orbit of <math>j</math>. In the case (a) above <math>A</math> is identity and <math>B(j) = j-1</math>, for (b) it's <math>A(i) = i+1</math> and <math>B</math> is the identity.

Mio: Undo revision 2876 by Mio (Talk)

2010-01-27T21:49:33Z

Undo revision 2876 by Mio (Talk)

← Older revision		Revision as of 14:49, 27 January 2010
Line 5:		Line 5:
	Here's the punchline: for a positive integer <math>n</math>, if we call <math>r(n)</math> the integer we get when we isolate the rightmost, i.e. the least significant, set bit in the binary representation of <math>n</math> (so e.g. <math>r(6) = 2</math> and <math>r(8) = 8</math>), then <math>A(i) = i + r(i)</math> and <math>B(i) = i - r(i)</math> are two such actions. What's more, in C and its ilk, <math>r(i)</math> is coded as <code>(-i)&i</code>.		Here's the punchline: for a positive integer <math>n</math>, if we call <math>r(n)</math> the integer we get when we isolate the rightmost, i.e. the least significant, set bit in the binary representation of <math>n</math> (so e.g. <math>r(6) = 2</math> and <math>r(8) = 8</math>), then <math>A(i) = i + r(i)</math> and <math>B(i) = i - r(i)</math> are two such actions. What's more, in C and its ilk, <math>r(i)</math> is coded as <code>(-i)&i</code>.

	Proof: <math>A</math> increases its argument while <math>B</math> decreases it, so if <math>x=y</math> then <math>A^0(x) = B^0(y)</math>, and that's the only intersection. If <math>x < y</math>, then binary representations of <math>x</math> and <math>y</math> are <math>y = a1b_y</math> and <math>x = a0b_x</math> where <math>a</math>, <math>b_x</math>, <math>b_y</math> are (possibly empty) binary sequences, and <math>b_x</math> and <math>b_y</math> are of same length <math>\|b\|</math>. (We may have had to pad the representation of <math>x</math> by zeros to the left as needed for this.) The action <math>B</math> unsets the rightmost set bit, so eventually <math>y</math> will under action of <math>B</math> arrive at <math>a10^{\|b\|}</math>, if it's not of that form to begin with. If <math>b_x</math> has no set bits, then one more action of <math>B</math> on <math>y</math> will make it equal to <math>x</math>. If <math>b_x</math> has set bits, then <math>A</math>, which turns a number of the form <math>z01^{m}0^{n}</math> into <math>z10^{m+n}</math> will eventually bring <math>x</math> to <math>a10^{\|b\|}</math>, which is where we left <math>y</math>. By the argument from the beginning, this is the only place the two orbits intersect. QED		Proof: <math>A</math> increases its argument while <math>B</math> decreases it, so if <math>x=y</math> then <math>A^0(x) = B^0(y)</math>, and that's the only intersection. If <math>x < y</math>, then binary representations of <math>x</math> and <math>y</math> are <math>y = a1b_y</math> and <math>x = a0b_x</math> where <math>a</math>, <math>b_x</math>, <math>b_y</math> are (possibly empty) binary sequences, and <math>b_x</math> and <math>b_y</math> are of same length <math>\|b\|</math>. We may have had to pad the representation of <math>x</math> by zeros to the left as needed for this. The action <math>B</math> unsets the rightmost set bit, so eventually <math>y</math> will under action of <math>B</math> arrive at <math>a10^{\|b\|}</math>, if it's not of that form to begin with. If <math>b_x</math> has no set bits, then one more action of <math>B</math> on <math>y</math> will make it equal to <math>x</math>. If <math>b_x</math> has set bits, then <math>A</math>, which turns a number of the form <math>z01^{m}0^{n}</math> into <math>z10^{m+n}</math> will eventually bring <math>x</math> to <math>a10^{\|b\|}</math>, which is where we left <math>y</math>. By the argument from the beginning, this is the only place the two orbits intersect. QED

	Here's a simple implementation in C++, add error checking as needed		Here's a simple implementation in C++, add error checking as needed

Mio at 21:47, 27 January 2010

2010-01-27T21:47:38Z

← Older revision		Revision as of 14:47, 27 January 2010
Line 5:		Line 5:
	Here's the punchline: for a positive integer <math>n</math>, if we call <math>r(n)</math> the integer we get when we isolate the rightmost, i.e. the least significant, set bit in the binary representation of <math>n</math> (so e.g. <math>r(6) = 2</math> and <math>r(8) = 8</math>), then <math>A(i) = i + r(i)</math> and <math>B(i) = i - r(i)</math> are two such actions. What's more, in C and its ilk, <math>r(i)</math> is coded as <code>(-i)&i</code>.		Here's the punchline: for a positive integer <math>n</math>, if we call <math>r(n)</math> the integer we get when we isolate the rightmost, i.e. the least significant, set bit in the binary representation of <math>n</math> (so e.g. <math>r(6) = 2</math> and <math>r(8) = 8</math>), then <math>A(i) = i + r(i)</math> and <math>B(i) = i - r(i)</math> are two such actions. What's more, in C and its ilk, <math>r(i)</math> is coded as <code>(-i)&i</code>.

	Proof: <math>A</math> increases its argument while <math>B</math> decreases it, so if <math>x=y</math> then <math>A^0(x) = B^0(y)</math>, and that's the only intersection. If <math>x < y</math>, then binary representations of <math>x</math> and <math>y</math> are <math>y = a1b_y</math> and <math>x = a0b_x</math> where <math>a</math>, <math>b_x</math>, <math>b_y</math> are (possibly empty) binary sequences, and <math>b_x</math> and <math>b_y</math> are of same length <math>\|b\|</math>. We may have had to pad the representation of <math>x</math> by zeros to the left as needed for this. The action <math>B</math> unsets the rightmost set bit, so eventually <math>y</math> will under action of <math>B</math> arrive at <math>a10^{\|b\|}</math>, if it's not of that form to begin with. If <math>b_x</math> has no set bits, then one more action of <math>B</math> on <math>y</math> will make it equal to <math>x</math>. If <math>b_x</math> has set bits, then <math>A</math>, which turns a number of the form <math>z01^{m}0^{n}</math> into <math>z10^{m+n}</math> will eventually bring <math>x</math> to <math>a10^{\|b\|}</math>, which is where we left <math>y</math>. By the argument from the beginning, this is the only place the two orbits intersect. QED		Proof: <math>A</math> increases its argument while <math>B</math> decreases it, so if <math>x=y</math> then <math>A^0(x) = B^0(y)</math>, and that's the only intersection. If <math>x < y</math>, then binary representations of <math>x</math> and <math>y</math> are <math>y = a1b_y</math> and <math>x = a0b_x</math> where <math>a</math>, <math>b_x</math>, <math>b_y</math> are (possibly empty) binary sequences, and <math>b_x</math> and <math>b_y</math> are of same length <math>\|b\|</math>. (We may have had to pad the representation of <math>x</math> by zeros to the left as needed for this.) The action <math>B</math> unsets the rightmost set bit, so eventually <math>y</math> will under action of <math>B</math> arrive at <math>a10^{\|b\|}</math>, if it's not of that form to begin with. If <math>b_x</math> has no set bits, then one more action of <math>B</math> on <math>y</math> will make it equal to <math>x</math>. If <math>b_x</math> has set bits, then <math>A</math>, which turns a number of the form <math>z01^{m}0^{n}</math> into <math>z10^{m+n}</math> will eventually bring <math>x</math> to <math>a10^{\|b\|}</math>, which is where we left <math>y</math>. By the argument from the beginning, this is the only place the two orbits intersect. QED

	Here's a simple implementation in C++, add error checking as needed		Here's a simple implementation in C++, add error checking as needed

Mio at 21:46, 27 January 2010

2010-01-27T21:46:22Z

← Older revision		Revision as of 14:46, 27 January 2010
Line 3:		Line 3:
	The idea is to have two actions on positive integers, say <math>A</math> and <math>B</math>, so that orbit of <math>x</math> under action of <math>A</math>, and orbit of <math>y</math> under action of <math>B</math> intersect in exactly one point if <math>x \leq y</math>, and none otherwise. We will maintain an array of size <math>N</math> with all elements initialized to 0. On each update of a sequence element <math>i</math>, update all the elements of the array with indices in the <math>A</math> orbit of <math>i</math> by that same amount. To retrieve the partial sum of elements <math>1</math> thru <math>j</math>, sum up all the elements from the array with indices in the <math>B</math> orbit of <math>j</math>. In the case (a) above <math>A</math> is identity and <math>B(j) = j-1</math>, for (b) it's <math>A(i) = i+1</math> and <math>B</math> is the identity.		The idea is to have two actions on positive integers, say <math>A</math> and <math>B</math>, so that orbit of <math>x</math> under action of <math>A</math>, and orbit of <math>y</math> under action of <math>B</math> intersect in exactly one point if <math>x \leq y</math>, and none otherwise. We will maintain an array of size <math>N</math> with all elements initialized to 0. On each update of a sequence element <math>i</math>, update all the elements of the array with indices in the <math>A</math> orbit of <math>i</math> by that same amount. To retrieve the partial sum of elements <math>1</math> thru <math>j</math>, sum up all the elements from the array with indices in the <math>B</math> orbit of <math>j</math>. In the case (a) above <math>A</math> is identity and <math>B(j) = j-1</math>, for (b) it's <math>A(i) = i+1</math> and <math>B</math> is the identity.

	Here's the punchline: for a positive integer <math>n</math>, if we call <math>r(n)</math> the integer we get when we isolate the rightmost, i.e. the least significant, set bit in the binary representation of <math>n</math> (so e.g. <math>r(6) = 2</math> and <math>r(8) = 8</math>), then <math>A(i) = i + r(i)</math> and <math>B(i) = i - r(i)</math> are two such actions. What's more, in C and its ilk, <math>r(i)</math> is coded as <code>-i&i</code>.		Here's the punchline: for a positive integer <math>n</math>, if we call <math>r(n)</math> the integer we get when we isolate the rightmost, i.e. the least significant, set bit in the binary representation of <math>n</math> (so e.g. <math>r(6) = 2</math> and <math>r(8) = 8</math>), then <math>A(i) = i + r(i)</math> and <math>B(i) = i - r(i)</math> are two such actions. What's more, in C and its ilk, <math>r(i)</math> is coded as <code>(-i)&i</code>.

	Proof: <math>A</math> increases its argument while <math>B</math> decreases it, so if <math>x=y</math> then <math>A^0(x) = B^0(y)</math>, and that's the only intersection. If <math>x < y</math>, then binary representations of <math>x</math> and <math>y</math> are <math>y = a1b_y</math> and <math>x = a0b_x</math> where <math>a</math>, <math>b_x</math>, <math>b_y</math> are (possibly empty) binary sequences, and <math>b_x</math> and <math>b_y</math> are of same length <math>\|b\|</math>. We may have had to pad the representation of <math>x</math> by zeros to the left as needed for this. The action <math>B</math> unsets the rightmost set bit, so eventually <math>y</math> will under action of <math>B</math> arrive at <math>a10^{\|b\|}</math>, if it's not of that form to begin with. If <math>b_x</math> has no set bits, then one more action of <math>B</math> on <math>y</math> will make it equal to <math>x</math>. If <math>b_x</math> has set bits, then <math>A</math>, which turns a number of the form <math>z01^{m}0^{n}</math> into <math>z10^{m+n}</math> will eventually bring <math>x</math> to <math>a10^{\|b\|}</math>, which is where we left <math>y</math>. By the argument from the beginning, this is the only place the two orbits intersect. QED		Proof: <math>A</math> increases its argument while <math>B</math> decreases it, so if <math>x=y</math> then <math>A^0(x) = B^0(y)</math>, and that's the only intersection. If <math>x < y</math>, then binary representations of <math>x</math> and <math>y</math> are <math>y = a1b_y</math> and <math>x = a0b_x</math> where <math>a</math>, <math>b_x</math>, <math>b_y</math> are (possibly empty) binary sequences, and <math>b_x</math> and <math>b_y</math> are of same length <math>\|b\|</math>. We may have had to pad the representation of <math>x</math> by zeros to the left as needed for this. The action <math>B</math> unsets the rightmost set bit, so eventually <math>y</math> will under action of <math>B</math> arrive at <math>a10^{\|b\|}</math>, if it's not of that form to begin with. If <math>b_x</math> has no set bits, then one more action of <math>B</math> on <math>y</math> will make it equal to <math>x</math>. If <math>b_x</math> has set bits, then <math>A</math>, which turns a number of the form <math>z01^{m}0^{n}</math> into <math>z10^{m+n}</math> will eventually bring <math>x</math> to <math>a10^{\|b\|}</math>, which is where we left <math>y</math>. By the argument from the beginning, this is the only place the two orbits intersect. QED

Mio at 22:09, 26 January 2010

2010-01-26T22:09:59Z

← Older revision		Revision as of 15:09, 26 January 2010
Line 1:		Line 1:
	The two straightforward ways to code updating and retrieval of partial sums of sequences are: (a) maintain the array of sequence elements - on each update of a sequence element update just the sequence element, and each time you need a partial sum you compute it from scratch, (b) maintain the array of partial sums - on each update of a sequence element update all the partial sums this element contributes to. In the case (a) update takes <math>O(1)</math> time and retrieval takes <math>O(N)</math>, in the case (b) update takes <math>O(N)</math> and retrieval <math>O(1)</math> time. <math>N</math> is the length of the sequence. The [http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf Fenwick tree] data structure (although it's not really a tree) has both update and retrieval taking <math>O(\log N)</math> time, while still using the same <math>O(N)</math> amount of space.		The two straightforward ways to code updating and retrieval of partial sums of sequences are: (a) maintain the array of sequence elements - on each update of a sequence element update just the sequence element, and each time you need a partial sum you compute it from scratch, (b) maintain the array of partial sums - on each update of a sequence element update all the partial sums this element contributes to. In the case (a) update takes <math>O(1)</math> time and retrieval takes <math>O(N)</math>, in the case (b) update takes <math>O(N)</math> and retrieval <math>O(1)</math> time. <math>N</math> is the length of the sequence. The [http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol24/issue3/spe884.pdf Fenwick tree] data structure (although it's not really a tree) has both update and retrieval taking <math>O(\log N)</math> time in the worst case, while still using the same <math>O(N)</math> amount of space.

	The idea is to have two actions on positive integers, say <math>A</math> and <math>B</math>, so that orbit of <math>x</math> under action of <math>A</math>, and orbit of <math>y</math> under action of <math>B</math> intersect in exactly one point if <math>x \leq y</math>, and none otherwise. We will maintain an array of size <math>N</math> with all elements initialized to 0. On each update of a sequence element <math>i</math>, update all the elements of the array with indices in the <math>A</math> orbit of <math>i</math> by that same amount. To retrieve the partial sum of elements <math>1</math> thru <math>j</math>, sum up all the elements from the array with indices in the <math>B</math> orbit of <math>j</math>. In the case (a) above <math>A</math> is identity and <math>B(j) = j-1</math>, for (b) it's <math>A(i) = i+1</math> and <math>B</math> is the identity.		The idea is to have two actions on positive integers, say <math>A</math> and <math>B</math>, so that orbit of <math>x</math> under action of <math>A</math>, and orbit of <math>y</math> under action of <math>B</math> intersect in exactly one point if <math>x \leq y</math>, and none otherwise. We will maintain an array of size <math>N</math> with all elements initialized to 0. On each update of a sequence element <math>i</math>, update all the elements of the array with indices in the <math>A</math> orbit of <math>i</math> by that same amount. To retrieve the partial sum of elements <math>1</math> thru <math>j</math>, sum up all the elements from the array with indices in the <math>B</math> orbit of <math>j</math>. In the case (a) above <math>A</math> is identity and <math>B(j) = j-1</math>, for (b) it's <math>A(i) = i+1</math> and <math>B</math> is the identity.