Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.