Michael Data

Dynamic Prefix Sum

check [http://www.ics.uci.edu/~mbannist/261/W8_T/]

Provide two operations

  • * update A[i] = x
  • * query A[0]+A[1]+…+A[i]
Naive Solutions
  • * Maintain A by itself, no other data
  • update operation is O(1) time
  • query is O(n) time
  • * Maintain A and another array P
  • P[i] = prefix-sum(i)
  • update operation is O(n) time
  • query is O(1) time
Good Solutions

Binary Tree Method

Array A is embedded in a binary tree B.

  • * Let q = a power of $2 \geq n$.
  • * Make an array B of size $n + q - 1$.
  • store A[i] in B[i+q-1]

B is an implicit binary tree with elements of A stored in its leaves. Each parent node in B stores the sum of its children. update() time = query() time = $O(\log n)$.

  • update(i,x)
  • j = i+q-1
  • B[j] = x
  • while j is not 0:
  • j = (j-1)/2
  • B[j] = B[2j+1] + B[2j+2]
  • query(i)
  • j = i+q-1
  • …………….

This structure can function with the addition operation replaced with any associative binary operation.

Bounds

Lower Bound for Sorting by Comparisons

There are n! different outcomes. So we need log_2(n!) = \theta(n log n) bits of information to distinguish between them. Each comparison provides one of those bits.

This bound can be proven more strongly through analysis that doesn't rely on comparison operations.

Cell Probe Model

By counting data transmissions between memory and the CPU in addition to comparison operations, can show lower bound than the comparison model. Data represented within cells or memory words.

  • memory is partitioned into words
  • reading or writing a word takes O(1) time
  • all information used in answering a query must be gathered by memory reads
  • no other form of persistent storage is allowed

Assume for simplicity that each cell in the array A is a single word in size.

Adversarial Proof

An adversary performs O(n) operations out of update() and query():

  • let n be an arbitrary power of 2
  • initilize all A[i] = 0
  • for i = 0,1,2,.. (n-1)
  • j = bit-reversal(i)
  • query(j)
  • update(j,Random())
  • bit-reversal(i)
  • replace the lsb and msb of all bits in input i
  • So for 8-bits,
  • 0→0
  • 1→4
  • 2→2
  • 3→6

The adversary simply queries and then updates in a manner which maximizes the number of operations required to keep the data structure consistent. Previous operation values are rendered useless to future operations by update().

If you analyze the dependencies through which one associative operation might take advantage of previous ones, you get a binary tree. This adversary effectively queries from the leaves of the tree upward, while invalidating the usefulness of data in all children before querying a node.

Correct responses will require O(n log n) input operations from the data structure.

Applications

Subarray Average Problem

Need to maintain array A[0…(n-1)] subject to 2 operations. This problem can be reduced to the Dynamic Prefix Sum problem.

  • set A[i] = x
  • normal array set
  • find average of A[i]…A[j]
  • (prefix-sum(j) - prefix-sum(i)) / (j-i)