MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi, is there any efficient techniques to do the following summation ?

Given a finite set $A$ containing $n$ integers $A=(x_1,x_2,…,x_n)$, where $x_i$ is an integer. Now there are $n$ subsets of $A$, denoted by $A_1, A_2, ... , A_n$. We want to calculate the summation for each subset, i.e., $b_i=\sum_{x_j \in A_i} x_j$.

Are there some efficient techniques to compute all the values of $b_1,..., b_n$ ?

share|cite|improve this question
This is too easy. And it is really a CS question. Ask on StackOverflow if you can't figure it out yourself. Plus, as stated, in the worst-case, one can't do better than $O(n^2)$, unless you know that each of the $A_i$ are uniformly bounded in size (by a constant). – Jacques Carette Apr 30 '12 at 12:33
If the same sets are to be preserved, and just the values change, you might consider dataflow analysis and common subexpressions. This is only if the computation pattern is to be repeated often enough to pay for the analysis. Gerhard "Ask Me About System Design" Paseman, 2012.04.30 – Gerhard Paseman Apr 30 '12 at 15:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.