How to find sum of maximum K elements in range in array





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}







4












$begingroup$


Recently, I came up to the following problem:



Given array $A$ of size $n$ and integer $k$, We should answer $Q$ questions of the type:
for given range $[l, r]$ we should find sum of the $k$ maximum elements over all $A_i$ such that $l leq i leq r$.



Trivial solution would be to sort all values in the range and iterate over the k biggest elements, however this has complexity $O(QNlog N)$. After some searching on the internet, I found out that this can be solved by segment trees, however I couldn't think of proper use of segment trees for this problem.



Is it possible to solve this problem in complexity better than $O(QNlog N)$










share|cite|improve this question











$endgroup$














  • $begingroup$
    There is eventually a trivial $O(Nk)$.
    $endgroup$
    – Vince
    May 20 at 8:07










  • $begingroup$
    Taking $Q = 1$, you are effectively not allowing any preprocessing at all.
    $endgroup$
    – Yuval Filmus
    May 20 at 9:52


















4












$begingroup$


Recently, I came up to the following problem:



Given array $A$ of size $n$ and integer $k$, We should answer $Q$ questions of the type:
for given range $[l, r]$ we should find sum of the $k$ maximum elements over all $A_i$ such that $l leq i leq r$.



Trivial solution would be to sort all values in the range and iterate over the k biggest elements, however this has complexity $O(QNlog N)$. After some searching on the internet, I found out that this can be solved by segment trees, however I couldn't think of proper use of segment trees for this problem.



Is it possible to solve this problem in complexity better than $O(QNlog N)$










share|cite|improve this question











$endgroup$














  • $begingroup$
    There is eventually a trivial $O(Nk)$.
    $endgroup$
    – Vince
    May 20 at 8:07










  • $begingroup$
    Taking $Q = 1$, you are effectively not allowing any preprocessing at all.
    $endgroup$
    – Yuval Filmus
    May 20 at 9:52














4












4








4


1



$begingroup$


Recently, I came up to the following problem:



Given array $A$ of size $n$ and integer $k$, We should answer $Q$ questions of the type:
for given range $[l, r]$ we should find sum of the $k$ maximum elements over all $A_i$ such that $l leq i leq r$.



Trivial solution would be to sort all values in the range and iterate over the k biggest elements, however this has complexity $O(QNlog N)$. After some searching on the internet, I found out that this can be solved by segment trees, however I couldn't think of proper use of segment trees for this problem.



Is it possible to solve this problem in complexity better than $O(QNlog N)$










share|cite|improve this question











$endgroup$




Recently, I came up to the following problem:



Given array $A$ of size $n$ and integer $k$, We should answer $Q$ questions of the type:
for given range $[l, r]$ we should find sum of the $k$ maximum elements over all $A_i$ such that $l leq i leq r$.



Trivial solution would be to sort all values in the range and iterate over the k biggest elements, however this has complexity $O(QNlog N)$. After some searching on the internet, I found out that this can be solved by segment trees, however I couldn't think of proper use of segment trees for this problem.



Is it possible to solve this problem in complexity better than $O(QNlog N)$







data-structures search-trees






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited May 20 at 9:25







someone12321

















asked May 20 at 7:40









someone12321someone12321

6853 silver badges13 bronze badges




6853 silver badges13 bronze badges















  • $begingroup$
    There is eventually a trivial $O(Nk)$.
    $endgroup$
    – Vince
    May 20 at 8:07










  • $begingroup$
    Taking $Q = 1$, you are effectively not allowing any preprocessing at all.
    $endgroup$
    – Yuval Filmus
    May 20 at 9:52


















  • $begingroup$
    There is eventually a trivial $O(Nk)$.
    $endgroup$
    – Vince
    May 20 at 8:07










  • $begingroup$
    Taking $Q = 1$, you are effectively not allowing any preprocessing at all.
    $endgroup$
    – Yuval Filmus
    May 20 at 9:52
















$begingroup$
There is eventually a trivial $O(Nk)$.
$endgroup$
– Vince
May 20 at 8:07




$begingroup$
There is eventually a trivial $O(Nk)$.
$endgroup$
– Vince
May 20 at 8:07












$begingroup$
Taking $Q = 1$, you are effectively not allowing any preprocessing at all.
$endgroup$
– Yuval Filmus
May 20 at 9:52




$begingroup$
Taking $Q = 1$, you are effectively not allowing any preprocessing at all.
$endgroup$
– Yuval Filmus
May 20 at 9:52










2 Answers
2






active

oldest

votes


















5












$begingroup$

This answer refers to the version of the question in which the interval $[l,r]$ refers to the values of the elements rather than their indices.



Without preprocessing: You can extract all elements in the range $[l,r]$ in linear time. You can then use the linear time selection algorithm to find the $k$'th largest element, and then you can easily find the sum of the $k$ maximum elements. Overall, you can answer each query in $O(n)$.



With preprocessing: Sort the array, and compute running sums. Given $l,r$, locate the subset of the array corresponding to this range using binary search, and then use the running sums to compute the sum of the $k$ largest elements in $O(1)$. Overall, this uses $O(nlog n)$ preprocessing and $O(log n)$ time per query.






share|cite|improve this answer











$endgroup$















  • $begingroup$
    @someone12321: do you mean O(n) is too slow, or that the constant factors are too high in any real implementation of it on normal CPUs? (too many passes over huge data costing a lot of memory bandwidth?)
    $endgroup$
    – Peter Cordes
    May 20 at 9:59










  • $begingroup$
    @PeterCordes For this version of the problem in the above answer, there is O(logN) solution per query.
    $endgroup$
    – someone12321
    May 20 at 10:14



















4












$begingroup$

This answer refers to the version of the question in which the range $[l,r]$ refers to indices of the array, and in which we have $Q$ queries. The question asked whether we could beat $O(Qnlog n)$.



Without preprocessing: Using the linear time selection algorithm, you can answer each query in $O(n)$, for a total of $O(Qn)$, which is better than $O(Qnlog n)$.



With preprocessing: Assume for simplicity that $n$ is a power of 2. We consider $log n$ layers, the first consisting of $n$ intervals of length 1, the second of $n/2$ intervals of length 2, and so on: the $k$th consists of $n/2^k$ intervals of length $k$. We sort all of the intervals in $O(nlog n)$ by "merging up the tree". At query time, we partition the input interval into $O(log n)$ stored intervals, and them return the answer in $O(klog n)$ by merging the $k$th largest elements from each.



We can improve the query time as follows. Along with the layered intervals, we also compute their running sums. Let us consider the $O(log n)$ layered intervals $I_1,ldots,I_m$ whose union is the given interval $[l,r]$. The $k$ largest elements of $[l,r]$ are composed of the $k_1,ldots,k_m$ largest elements in $I_1,ldots,I_m$. If we could determine $k_1,ldots,k_m$, then we could compute the answer in $O(m) = O(log n)$ using the running sums.



We can determine $k_1,ldots,k_m$ as follows. For each element $x in I_1$, we can count how many elements are larger than $x$ in time $O(mlog k) = O(log n log k)$ using binary search. By doing binary search on the top $k$ elements of $I_1$, we can determine $k_1$ in time $O(log n log^2 k)$. Continuing in this way, we can determine $k_1,ldots,k_m$ in time $O(log^2 n log^2 k)$.



This solution has preprocessing time $O(nlog n)$ and query time $O(log^2 n log^2 k)$.



We can obtain other tradeoffs by varying the fan-in of the tree. Suppose that the fan-in is $n^{1/d}$. For each internal node in the tree, we sort each interval-of-intervals within its children. At level $i$ we have $n^{i/d}$ vertices, each has $n^{2/d}$ intervals-of-intervals, each of length at most $n^{1-i/d}$, so sorting all intervals-of-intervals at level $i$ takes time $n^{1+2/d}$, for a total preprocessing time of $O(dn^{1+2/d})$. In query time, we can break $[l,r]$ into a union of $O(d)$ intervals, for a total query time of $O(d^2log^2 k)$.



Stated differently, for each $epsilon > 0$ this gives an algorithm with preprocessing time $O(epsilon^{-1} n^{1+epsilon})$ and query time $O(epsilon^{-2} log^2 k)$.






share|cite|improve this answer











$endgroup$















  • $begingroup$
    I don't think that this improves the things a lot, since k can be up to n.
    $endgroup$
    – someone12321
    May 20 at 10:16










  • $begingroup$
    You can precompute all the answers in $O(n^3)$, and then the time per query is $O(1)$.
    $endgroup$
    – Yuval Filmus
    May 20 at 10:22










  • $begingroup$
    We can even precompute all the answer in $O(n^2 log n)$ however this is very slow and memory consuming solution.
    $endgroup$
    – someone12321
    May 20 at 10:25










  • $begingroup$
    How about query time $O(log^4 n)$?
    $endgroup$
    – Yuval Filmus
    May 20 at 10:45










  • $begingroup$
    Recently, I read about persistent segment tree, and I think that we can solve this with persistent segment tree, for each prefix of the array we store one segment tree whose leafs actually represent the count of some number $x$. Then to find the sum we actually do binary search on two prefixes of all the roots we save, however I'm not really sure how to finish this and implement since we can have bigger numbers and even duplicates. Careful implementations can run in $O(log N)$
    $endgroup$
    – someone12321
    May 20 at 13:12
















Your Answer








StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f109579%2fhow-to-find-sum-of-maximum-k-elements-in-range-in-array%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









5












$begingroup$

This answer refers to the version of the question in which the interval $[l,r]$ refers to the values of the elements rather than their indices.



Without preprocessing: You can extract all elements in the range $[l,r]$ in linear time. You can then use the linear time selection algorithm to find the $k$'th largest element, and then you can easily find the sum of the $k$ maximum elements. Overall, you can answer each query in $O(n)$.



With preprocessing: Sort the array, and compute running sums. Given $l,r$, locate the subset of the array corresponding to this range using binary search, and then use the running sums to compute the sum of the $k$ largest elements in $O(1)$. Overall, this uses $O(nlog n)$ preprocessing and $O(log n)$ time per query.






share|cite|improve this answer











$endgroup$















  • $begingroup$
    @someone12321: do you mean O(n) is too slow, or that the constant factors are too high in any real implementation of it on normal CPUs? (too many passes over huge data costing a lot of memory bandwidth?)
    $endgroup$
    – Peter Cordes
    May 20 at 9:59










  • $begingroup$
    @PeterCordes For this version of the problem in the above answer, there is O(logN) solution per query.
    $endgroup$
    – someone12321
    May 20 at 10:14
















5












$begingroup$

This answer refers to the version of the question in which the interval $[l,r]$ refers to the values of the elements rather than their indices.



Without preprocessing: You can extract all elements in the range $[l,r]$ in linear time. You can then use the linear time selection algorithm to find the $k$'th largest element, and then you can easily find the sum of the $k$ maximum elements. Overall, you can answer each query in $O(n)$.



With preprocessing: Sort the array, and compute running sums. Given $l,r$, locate the subset of the array corresponding to this range using binary search, and then use the running sums to compute the sum of the $k$ largest elements in $O(1)$. Overall, this uses $O(nlog n)$ preprocessing and $O(log n)$ time per query.






share|cite|improve this answer











$endgroup$















  • $begingroup$
    @someone12321: do you mean O(n) is too slow, or that the constant factors are too high in any real implementation of it on normal CPUs? (too many passes over huge data costing a lot of memory bandwidth?)
    $endgroup$
    – Peter Cordes
    May 20 at 9:59










  • $begingroup$
    @PeterCordes For this version of the problem in the above answer, there is O(logN) solution per query.
    $endgroup$
    – someone12321
    May 20 at 10:14














5












5








5





$begingroup$

This answer refers to the version of the question in which the interval $[l,r]$ refers to the values of the elements rather than their indices.



Without preprocessing: You can extract all elements in the range $[l,r]$ in linear time. You can then use the linear time selection algorithm to find the $k$'th largest element, and then you can easily find the sum of the $k$ maximum elements. Overall, you can answer each query in $O(n)$.



With preprocessing: Sort the array, and compute running sums. Given $l,r$, locate the subset of the array corresponding to this range using binary search, and then use the running sums to compute the sum of the $k$ largest elements in $O(1)$. Overall, this uses $O(nlog n)$ preprocessing and $O(log n)$ time per query.






share|cite|improve this answer











$endgroup$



This answer refers to the version of the question in which the interval $[l,r]$ refers to the values of the elements rather than their indices.



Without preprocessing: You can extract all elements in the range $[l,r]$ in linear time. You can then use the linear time selection algorithm to find the $k$'th largest element, and then you can easily find the sum of the $k$ maximum elements. Overall, you can answer each query in $O(n)$.



With preprocessing: Sort the array, and compute running sums. Given $l,r$, locate the subset of the array corresponding to this range using binary search, and then use the running sums to compute the sum of the $k$ largest elements in $O(1)$. Overall, this uses $O(nlog n)$ preprocessing and $O(log n)$ time per query.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited May 20 at 9:50

























answered May 20 at 8:32









Yuval FilmusYuval Filmus

205k15 gold badges200 silver badges365 bronze badges




205k15 gold badges200 silver badges365 bronze badges















  • $begingroup$
    @someone12321: do you mean O(n) is too slow, or that the constant factors are too high in any real implementation of it on normal CPUs? (too many passes over huge data costing a lot of memory bandwidth?)
    $endgroup$
    – Peter Cordes
    May 20 at 9:59










  • $begingroup$
    @PeterCordes For this version of the problem in the above answer, there is O(logN) solution per query.
    $endgroup$
    – someone12321
    May 20 at 10:14


















  • $begingroup$
    @someone12321: do you mean O(n) is too slow, or that the constant factors are too high in any real implementation of it on normal CPUs? (too many passes over huge data costing a lot of memory bandwidth?)
    $endgroup$
    – Peter Cordes
    May 20 at 9:59










  • $begingroup$
    @PeterCordes For this version of the problem in the above answer, there is O(logN) solution per query.
    $endgroup$
    – someone12321
    May 20 at 10:14
















$begingroup$
@someone12321: do you mean O(n) is too slow, or that the constant factors are too high in any real implementation of it on normal CPUs? (too many passes over huge data costing a lot of memory bandwidth?)
$endgroup$
– Peter Cordes
May 20 at 9:59




$begingroup$
@someone12321: do you mean O(n) is too slow, or that the constant factors are too high in any real implementation of it on normal CPUs? (too many passes over huge data costing a lot of memory bandwidth?)
$endgroup$
– Peter Cordes
May 20 at 9:59












$begingroup$
@PeterCordes For this version of the problem in the above answer, there is O(logN) solution per query.
$endgroup$
– someone12321
May 20 at 10:14




$begingroup$
@PeterCordes For this version of the problem in the above answer, there is O(logN) solution per query.
$endgroup$
– someone12321
May 20 at 10:14













4












$begingroup$

This answer refers to the version of the question in which the range $[l,r]$ refers to indices of the array, and in which we have $Q$ queries. The question asked whether we could beat $O(Qnlog n)$.



Without preprocessing: Using the linear time selection algorithm, you can answer each query in $O(n)$, for a total of $O(Qn)$, which is better than $O(Qnlog n)$.



With preprocessing: Assume for simplicity that $n$ is a power of 2. We consider $log n$ layers, the first consisting of $n$ intervals of length 1, the second of $n/2$ intervals of length 2, and so on: the $k$th consists of $n/2^k$ intervals of length $k$. We sort all of the intervals in $O(nlog n)$ by "merging up the tree". At query time, we partition the input interval into $O(log n)$ stored intervals, and them return the answer in $O(klog n)$ by merging the $k$th largest elements from each.



We can improve the query time as follows. Along with the layered intervals, we also compute their running sums. Let us consider the $O(log n)$ layered intervals $I_1,ldots,I_m$ whose union is the given interval $[l,r]$. The $k$ largest elements of $[l,r]$ are composed of the $k_1,ldots,k_m$ largest elements in $I_1,ldots,I_m$. If we could determine $k_1,ldots,k_m$, then we could compute the answer in $O(m) = O(log n)$ using the running sums.



We can determine $k_1,ldots,k_m$ as follows. For each element $x in I_1$, we can count how many elements are larger than $x$ in time $O(mlog k) = O(log n log k)$ using binary search. By doing binary search on the top $k$ elements of $I_1$, we can determine $k_1$ in time $O(log n log^2 k)$. Continuing in this way, we can determine $k_1,ldots,k_m$ in time $O(log^2 n log^2 k)$.



This solution has preprocessing time $O(nlog n)$ and query time $O(log^2 n log^2 k)$.



We can obtain other tradeoffs by varying the fan-in of the tree. Suppose that the fan-in is $n^{1/d}$. For each internal node in the tree, we sort each interval-of-intervals within its children. At level $i$ we have $n^{i/d}$ vertices, each has $n^{2/d}$ intervals-of-intervals, each of length at most $n^{1-i/d}$, so sorting all intervals-of-intervals at level $i$ takes time $n^{1+2/d}$, for a total preprocessing time of $O(dn^{1+2/d})$. In query time, we can break $[l,r]$ into a union of $O(d)$ intervals, for a total query time of $O(d^2log^2 k)$.



Stated differently, for each $epsilon > 0$ this gives an algorithm with preprocessing time $O(epsilon^{-1} n^{1+epsilon})$ and query time $O(epsilon^{-2} log^2 k)$.






share|cite|improve this answer











$endgroup$















  • $begingroup$
    I don't think that this improves the things a lot, since k can be up to n.
    $endgroup$
    – someone12321
    May 20 at 10:16










  • $begingroup$
    You can precompute all the answers in $O(n^3)$, and then the time per query is $O(1)$.
    $endgroup$
    – Yuval Filmus
    May 20 at 10:22










  • $begingroup$
    We can even precompute all the answer in $O(n^2 log n)$ however this is very slow and memory consuming solution.
    $endgroup$
    – someone12321
    May 20 at 10:25










  • $begingroup$
    How about query time $O(log^4 n)$?
    $endgroup$
    – Yuval Filmus
    May 20 at 10:45










  • $begingroup$
    Recently, I read about persistent segment tree, and I think that we can solve this with persistent segment tree, for each prefix of the array we store one segment tree whose leafs actually represent the count of some number $x$. Then to find the sum we actually do binary search on two prefixes of all the roots we save, however I'm not really sure how to finish this and implement since we can have bigger numbers and even duplicates. Careful implementations can run in $O(log N)$
    $endgroup$
    – someone12321
    May 20 at 13:12


















4












$begingroup$

This answer refers to the version of the question in which the range $[l,r]$ refers to indices of the array, and in which we have $Q$ queries. The question asked whether we could beat $O(Qnlog n)$.



Without preprocessing: Using the linear time selection algorithm, you can answer each query in $O(n)$, for a total of $O(Qn)$, which is better than $O(Qnlog n)$.



With preprocessing: Assume for simplicity that $n$ is a power of 2. We consider $log n$ layers, the first consisting of $n$ intervals of length 1, the second of $n/2$ intervals of length 2, and so on: the $k$th consists of $n/2^k$ intervals of length $k$. We sort all of the intervals in $O(nlog n)$ by "merging up the tree". At query time, we partition the input interval into $O(log n)$ stored intervals, and them return the answer in $O(klog n)$ by merging the $k$th largest elements from each.



We can improve the query time as follows. Along with the layered intervals, we also compute their running sums. Let us consider the $O(log n)$ layered intervals $I_1,ldots,I_m$ whose union is the given interval $[l,r]$. The $k$ largest elements of $[l,r]$ are composed of the $k_1,ldots,k_m$ largest elements in $I_1,ldots,I_m$. If we could determine $k_1,ldots,k_m$, then we could compute the answer in $O(m) = O(log n)$ using the running sums.



We can determine $k_1,ldots,k_m$ as follows. For each element $x in I_1$, we can count how many elements are larger than $x$ in time $O(mlog k) = O(log n log k)$ using binary search. By doing binary search on the top $k$ elements of $I_1$, we can determine $k_1$ in time $O(log n log^2 k)$. Continuing in this way, we can determine $k_1,ldots,k_m$ in time $O(log^2 n log^2 k)$.



This solution has preprocessing time $O(nlog n)$ and query time $O(log^2 n log^2 k)$.



We can obtain other tradeoffs by varying the fan-in of the tree. Suppose that the fan-in is $n^{1/d}$. For each internal node in the tree, we sort each interval-of-intervals within its children. At level $i$ we have $n^{i/d}$ vertices, each has $n^{2/d}$ intervals-of-intervals, each of length at most $n^{1-i/d}$, so sorting all intervals-of-intervals at level $i$ takes time $n^{1+2/d}$, for a total preprocessing time of $O(dn^{1+2/d})$. In query time, we can break $[l,r]$ into a union of $O(d)$ intervals, for a total query time of $O(d^2log^2 k)$.



Stated differently, for each $epsilon > 0$ this gives an algorithm with preprocessing time $O(epsilon^{-1} n^{1+epsilon})$ and query time $O(epsilon^{-2} log^2 k)$.






share|cite|improve this answer











$endgroup$















  • $begingroup$
    I don't think that this improves the things a lot, since k can be up to n.
    $endgroup$
    – someone12321
    May 20 at 10:16










  • $begingroup$
    You can precompute all the answers in $O(n^3)$, and then the time per query is $O(1)$.
    $endgroup$
    – Yuval Filmus
    May 20 at 10:22










  • $begingroup$
    We can even precompute all the answer in $O(n^2 log n)$ however this is very slow and memory consuming solution.
    $endgroup$
    – someone12321
    May 20 at 10:25










  • $begingroup$
    How about query time $O(log^4 n)$?
    $endgroup$
    – Yuval Filmus
    May 20 at 10:45










  • $begingroup$
    Recently, I read about persistent segment tree, and I think that we can solve this with persistent segment tree, for each prefix of the array we store one segment tree whose leafs actually represent the count of some number $x$. Then to find the sum we actually do binary search on two prefixes of all the roots we save, however I'm not really sure how to finish this and implement since we can have bigger numbers and even duplicates. Careful implementations can run in $O(log N)$
    $endgroup$
    – someone12321
    May 20 at 13:12
















4












4








4





$begingroup$

This answer refers to the version of the question in which the range $[l,r]$ refers to indices of the array, and in which we have $Q$ queries. The question asked whether we could beat $O(Qnlog n)$.



Without preprocessing: Using the linear time selection algorithm, you can answer each query in $O(n)$, for a total of $O(Qn)$, which is better than $O(Qnlog n)$.



With preprocessing: Assume for simplicity that $n$ is a power of 2. We consider $log n$ layers, the first consisting of $n$ intervals of length 1, the second of $n/2$ intervals of length 2, and so on: the $k$th consists of $n/2^k$ intervals of length $k$. We sort all of the intervals in $O(nlog n)$ by "merging up the tree". At query time, we partition the input interval into $O(log n)$ stored intervals, and them return the answer in $O(klog n)$ by merging the $k$th largest elements from each.



We can improve the query time as follows. Along with the layered intervals, we also compute their running sums. Let us consider the $O(log n)$ layered intervals $I_1,ldots,I_m$ whose union is the given interval $[l,r]$. The $k$ largest elements of $[l,r]$ are composed of the $k_1,ldots,k_m$ largest elements in $I_1,ldots,I_m$. If we could determine $k_1,ldots,k_m$, then we could compute the answer in $O(m) = O(log n)$ using the running sums.



We can determine $k_1,ldots,k_m$ as follows. For each element $x in I_1$, we can count how many elements are larger than $x$ in time $O(mlog k) = O(log n log k)$ using binary search. By doing binary search on the top $k$ elements of $I_1$, we can determine $k_1$ in time $O(log n log^2 k)$. Continuing in this way, we can determine $k_1,ldots,k_m$ in time $O(log^2 n log^2 k)$.



This solution has preprocessing time $O(nlog n)$ and query time $O(log^2 n log^2 k)$.



We can obtain other tradeoffs by varying the fan-in of the tree. Suppose that the fan-in is $n^{1/d}$. For each internal node in the tree, we sort each interval-of-intervals within its children. At level $i$ we have $n^{i/d}$ vertices, each has $n^{2/d}$ intervals-of-intervals, each of length at most $n^{1-i/d}$, so sorting all intervals-of-intervals at level $i$ takes time $n^{1+2/d}$, for a total preprocessing time of $O(dn^{1+2/d})$. In query time, we can break $[l,r]$ into a union of $O(d)$ intervals, for a total query time of $O(d^2log^2 k)$.



Stated differently, for each $epsilon > 0$ this gives an algorithm with preprocessing time $O(epsilon^{-1} n^{1+epsilon})$ and query time $O(epsilon^{-2} log^2 k)$.






share|cite|improve this answer











$endgroup$



This answer refers to the version of the question in which the range $[l,r]$ refers to indices of the array, and in which we have $Q$ queries. The question asked whether we could beat $O(Qnlog n)$.



Without preprocessing: Using the linear time selection algorithm, you can answer each query in $O(n)$, for a total of $O(Qn)$, which is better than $O(Qnlog n)$.



With preprocessing: Assume for simplicity that $n$ is a power of 2. We consider $log n$ layers, the first consisting of $n$ intervals of length 1, the second of $n/2$ intervals of length 2, and so on: the $k$th consists of $n/2^k$ intervals of length $k$. We sort all of the intervals in $O(nlog n)$ by "merging up the tree". At query time, we partition the input interval into $O(log n)$ stored intervals, and them return the answer in $O(klog n)$ by merging the $k$th largest elements from each.



We can improve the query time as follows. Along with the layered intervals, we also compute their running sums. Let us consider the $O(log n)$ layered intervals $I_1,ldots,I_m$ whose union is the given interval $[l,r]$. The $k$ largest elements of $[l,r]$ are composed of the $k_1,ldots,k_m$ largest elements in $I_1,ldots,I_m$. If we could determine $k_1,ldots,k_m$, then we could compute the answer in $O(m) = O(log n)$ using the running sums.



We can determine $k_1,ldots,k_m$ as follows. For each element $x in I_1$, we can count how many elements are larger than $x$ in time $O(mlog k) = O(log n log k)$ using binary search. By doing binary search on the top $k$ elements of $I_1$, we can determine $k_1$ in time $O(log n log^2 k)$. Continuing in this way, we can determine $k_1,ldots,k_m$ in time $O(log^2 n log^2 k)$.



This solution has preprocessing time $O(nlog n)$ and query time $O(log^2 n log^2 k)$.



We can obtain other tradeoffs by varying the fan-in of the tree. Suppose that the fan-in is $n^{1/d}$. For each internal node in the tree, we sort each interval-of-intervals within its children. At level $i$ we have $n^{i/d}$ vertices, each has $n^{2/d}$ intervals-of-intervals, each of length at most $n^{1-i/d}$, so sorting all intervals-of-intervals at level $i$ takes time $n^{1+2/d}$, for a total preprocessing time of $O(dn^{1+2/d})$. In query time, we can break $[l,r]$ into a union of $O(d)$ intervals, for a total query time of $O(d^2log^2 k)$.



Stated differently, for each $epsilon > 0$ this gives an algorithm with preprocessing time $O(epsilon^{-1} n^{1+epsilon})$ and query time $O(epsilon^{-2} log^2 k)$.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited May 20 at 10:57

























answered May 20 at 9:53









Yuval FilmusYuval Filmus

205k15 gold badges200 silver badges365 bronze badges




205k15 gold badges200 silver badges365 bronze badges















  • $begingroup$
    I don't think that this improves the things a lot, since k can be up to n.
    $endgroup$
    – someone12321
    May 20 at 10:16










  • $begingroup$
    You can precompute all the answers in $O(n^3)$, and then the time per query is $O(1)$.
    $endgroup$
    – Yuval Filmus
    May 20 at 10:22










  • $begingroup$
    We can even precompute all the answer in $O(n^2 log n)$ however this is very slow and memory consuming solution.
    $endgroup$
    – someone12321
    May 20 at 10:25










  • $begingroup$
    How about query time $O(log^4 n)$?
    $endgroup$
    – Yuval Filmus
    May 20 at 10:45










  • $begingroup$
    Recently, I read about persistent segment tree, and I think that we can solve this with persistent segment tree, for each prefix of the array we store one segment tree whose leafs actually represent the count of some number $x$. Then to find the sum we actually do binary search on two prefixes of all the roots we save, however I'm not really sure how to finish this and implement since we can have bigger numbers and even duplicates. Careful implementations can run in $O(log N)$
    $endgroup$
    – someone12321
    May 20 at 13:12




















  • $begingroup$
    I don't think that this improves the things a lot, since k can be up to n.
    $endgroup$
    – someone12321
    May 20 at 10:16










  • $begingroup$
    You can precompute all the answers in $O(n^3)$, and then the time per query is $O(1)$.
    $endgroup$
    – Yuval Filmus
    May 20 at 10:22










  • $begingroup$
    We can even precompute all the answer in $O(n^2 log n)$ however this is very slow and memory consuming solution.
    $endgroup$
    – someone12321
    May 20 at 10:25










  • $begingroup$
    How about query time $O(log^4 n)$?
    $endgroup$
    – Yuval Filmus
    May 20 at 10:45










  • $begingroup$
    Recently, I read about persistent segment tree, and I think that we can solve this with persistent segment tree, for each prefix of the array we store one segment tree whose leafs actually represent the count of some number $x$. Then to find the sum we actually do binary search on two prefixes of all the roots we save, however I'm not really sure how to finish this and implement since we can have bigger numbers and even duplicates. Careful implementations can run in $O(log N)$
    $endgroup$
    – someone12321
    May 20 at 13:12


















$begingroup$
I don't think that this improves the things a lot, since k can be up to n.
$endgroup$
– someone12321
May 20 at 10:16




$begingroup$
I don't think that this improves the things a lot, since k can be up to n.
$endgroup$
– someone12321
May 20 at 10:16












$begingroup$
You can precompute all the answers in $O(n^3)$, and then the time per query is $O(1)$.
$endgroup$
– Yuval Filmus
May 20 at 10:22




$begingroup$
You can precompute all the answers in $O(n^3)$, and then the time per query is $O(1)$.
$endgroup$
– Yuval Filmus
May 20 at 10:22












$begingroup$
We can even precompute all the answer in $O(n^2 log n)$ however this is very slow and memory consuming solution.
$endgroup$
– someone12321
May 20 at 10:25




$begingroup$
We can even precompute all the answer in $O(n^2 log n)$ however this is very slow and memory consuming solution.
$endgroup$
– someone12321
May 20 at 10:25












$begingroup$
How about query time $O(log^4 n)$?
$endgroup$
– Yuval Filmus
May 20 at 10:45




$begingroup$
How about query time $O(log^4 n)$?
$endgroup$
– Yuval Filmus
May 20 at 10:45












$begingroup$
Recently, I read about persistent segment tree, and I think that we can solve this with persistent segment tree, for each prefix of the array we store one segment tree whose leafs actually represent the count of some number $x$. Then to find the sum we actually do binary search on two prefixes of all the roots we save, however I'm not really sure how to finish this and implement since we can have bigger numbers and even duplicates. Careful implementations can run in $O(log N)$
$endgroup$
– someone12321
May 20 at 13:12






$begingroup$
Recently, I read about persistent segment tree, and I think that we can solve this with persistent segment tree, for each prefix of the array we store one segment tree whose leafs actually represent the count of some number $x$. Then to find the sum we actually do binary search on two prefixes of all the roots we save, however I'm not really sure how to finish this and implement since we can have bigger numbers and even duplicates. Careful implementations can run in $O(log N)$
$endgroup$
– someone12321
May 20 at 13:12




















draft saved

draft discarded




















































Thanks for contributing an answer to Computer Science Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f109579%2fhow-to-find-sum-of-maximum-k-elements-in-range-in-array%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Færeyskur hestur Heimild | Tengill | Tilvísanir | LeiðsagnarvalRossið - síða um færeyska hrossið á færeyskuGott ár hjá færeyska hestinum

He _____ here since 1970 . Answer needed [closed]What does “since he was so high” mean?Meaning of “catch birds for”?How do I ensure “since” takes the meaning I want?“Who cares here” meaningWhat does “right round toward” mean?the time tense (had now been detected)What does the phrase “ring around the roses” mean here?Correct usage of “visited upon”Meaning of “foiled rail sabotage bid”It was the third time I had gone to Rome or It is the third time I had been to Rome

Slayer Innehåll Historia | Stil, komposition och lyrik | Bandets betydelse och framgångar | Sidoprojekt och samarbeten | Kontroverser | Medlemmar | Utmärkelser och nomineringar | Turnéer och festivaler | Diskografi | Referenser | Externa länkar | Navigeringsmenywww.slayer.net”Metal Massacre vol. 1””Metal Massacre vol. 3””Metal Massacre Volume III””Show No Mercy””Haunting the Chapel””Live Undead””Hell Awaits””Reign in Blood””Reign in Blood””Gold & Platinum – Reign in Blood””Golden Gods Awards Winners”originalet”Kerrang! Hall Of Fame””Slayer Looks Back On 37-Year Career In New Video Series: Part Two””South of Heaven””Gold & Platinum – South of Heaven””Seasons in the Abyss””Gold & Platinum - Seasons in the Abyss””Divine Intervention””Divine Intervention - Release group by Slayer””Gold & Platinum - Divine Intervention””Live Intrusion””Undisputed Attitude””Abolish Government/Superficial Love””Release “Slatanic Slaughter: A Tribute to Slayer” by Various Artists””Diabolus in Musica””Soundtrack to the Apocalypse””God Hates Us All””Systematic - Relationships””War at the Warfield””Gold & Platinum - War at the Warfield””Soundtrack to the Apocalypse””Gold & Platinum - Still Reigning””Metallica, Slayer, Iron Mauden Among Winners At Metal Hammer Awards””Eternal Pyre””Eternal Pyre - Slayer release group””Eternal Pyre””Metal Storm Awards 2006””Kerrang! Hall Of Fame””Slayer Wins 'Best Metal' Grammy Award””Slayer Guitarist Jeff Hanneman Dies””Bullet-For My Valentine booed at Metal Hammer Golden Gods Awards””Unholy Aliance””The End Of Slayer?””Slayer: We Could Thrash Out Two More Albums If We're Fast Enough...””'The Unholy Alliance: Chapter III' UK Dates Added”originalet”Megadeth And Slayer To Co-Headline 'Canadian Carnage' Trek”originalet”World Painted Blood””Release “World Painted Blood” by Slayer””Metallica Heading To Cinemas””Slayer, Megadeth To Join Forces For 'European Carnage' Tour - Dec. 18, 2010”originalet”Slayer's Hanneman Contracts Acute Infection; Band To Bring In Guest Guitarist””Cannibal Corpse's Pat O'Brien Will Step In As Slayer's Guest Guitarist”originalet”Slayer’s Jeff Hanneman Dead at 49””Dave Lombardo Says He Made Only $67,000 In 2011 While Touring With Slayer””Slayer: We Do Not Agree With Dave Lombardo's Substance Or Timeline Of Events””Slayer Welcomes Drummer Paul Bostaph Back To The Fold””Slayer Hope to Unveil Never-Before-Heard Jeff Hanneman Material on Next Album””Slayer Debut New Song 'Implode' During Surprise Golden Gods Appearance””Release group Repentless by Slayer””Repentless - Slayer - Credits””Slayer””Metal Storm Awards 2015””Slayer - to release comic book "Repentless #1"””Slayer To Release 'Repentless' 6.66" Vinyl Box Set””BREAKING NEWS: Slayer Announce Farewell Tour””Slayer Recruit Lamb of God, Anthrax, Behemoth + Testament for Final Tour””Slayer lägger ner efter 37 år””Slayer Announces Second North American Leg Of 'Final' Tour””Final World Tour””Slayer Announces Final European Tour With Lamb of God, Anthrax And Obituary””Slayer To Tour Europe With Lamb of God, Anthrax And Obituary””Slayer To Play 'Last French Show Ever' At Next Year's Hellfst””Slayer's Final World Tour Will Extend Into 2019””Death Angel's Rob Cavestany On Slayer's 'Farewell' Tour: 'Some Of Us Could See This Coming'””Testament Has No Plans To Retire Anytime Soon, Says Chuck Billy””Anthrax's Scott Ian On Slayer's 'Farewell' Tour Plans: 'I Was Surprised And I Wasn't Surprised'””Slayer””Slayer's Morbid Schlock””Review/Rock; For Slayer, the Mania Is the Message””Slayer - Biography””Slayer - Reign In Blood”originalet”Dave Lombardo””An exclusive oral history of Slayer”originalet”Exclusive! Interview With Slayer Guitarist Jeff Hanneman”originalet”Thinking Out Loud: Slayer's Kerry King on hair metal, Satan and being polite””Slayer Lyrics””Slayer - Biography””Most influential artists for extreme metal music””Slayer - Reign in Blood””Slayer guitarist Jeff Hanneman dies aged 49””Slatanic Slaughter: A Tribute to Slayer””Gateway to Hell: A Tribute to Slayer””Covered In Blood””Slayer: The Origins of Thrash in San Francisco, CA.””Why They Rule - #6 Slayer”originalet”Guitar World's 100 Greatest Heavy Metal Guitarists Of All Time”originalet”The fans have spoken: Slayer comes out on top in readers' polls”originalet”Tribute to Jeff Hanneman (1964-2013)””Lamb Of God Frontman: We Sound Like A Slayer Rip-Off””BEHEMOTH Frontman Pays Tribute To SLAYER's JEFF HANNEMAN””Slayer, Hatebreed Doing Double Duty On This Year's Ozzfest””System of a Down””Lacuna Coil’s Andrea Ferro Talks Influences, Skateboarding, Band Origins + More””Slayer - Reign in Blood””Into The Lungs of Hell””Slayer rules - en utställning om fans””Slayer and Their Fans Slashed Through a No-Holds-Barred Night at Gas Monkey””Home””Slayer””Gold & Platinum - The Big 4 Live from Sofia, Bulgaria””Exclusive! Interview With Slayer Guitarist Kerry King””2008-02-23: Wiltern, Los Angeles, CA, USA””Slayer's Kerry King To Perform With Megadeth Tonight! - Oct. 21, 2010”originalet”Dave Lombardo - Biography”Slayer Case DismissedArkiveradUltimate Classic Rock: Slayer guitarist Jeff Hanneman dead at 49.”Slayer: "We could never do any thing like Some Kind Of Monster..."””Cannibal Corpse'S Pat O'Brien Will Step In As Slayer'S Guest Guitarist | The Official Slayer Site”originalet”Slayer Wins 'Best Metal' Grammy Award””Slayer Guitarist Jeff Hanneman Dies””Kerrang! Awards 2006 Blog: Kerrang! Hall Of Fame””Kerrang! Awards 2013: Kerrang! Legend”originalet”Metallica, Slayer, Iron Maien Among Winners At Metal Hammer Awards””Metal Hammer Golden Gods Awards””Bullet For My Valentine Booed At Metal Hammer Golden Gods Awards””Metal Storm Awards 2006””Metal Storm Awards 2015””Slayer's Concert History””Slayer - Relationships””Slayer - Releases”Slayers officiella webbplatsSlayer på MusicBrainzOfficiell webbplatsSlayerSlayerr1373445760000 0001 1540 47353068615-5086262726cb13906545x(data)6033143kn20030215029