find sum of first i/2 smallest numbers in array at index i

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 days
Register now »

*has extra registration

→ Streams

DP Bitmask - Topic Stream

By Shayan

Before stream 04:21:13

View all →

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

anucode's blog

find sum of first i/2 smallest numbers in array at index i

By anucode, history, 6 months ago, In English

We have an array of integer and we want at evey odd index i we have to find sum of first i/2 smallest number from index 1 to index i

lets

At index 1 sum of 0 smallest number

At index 3 sum of first one smallest number

At index 5 sum of first two smallest number

At index 7 sum of first three smallest number

At index 9 sum of first four smallest number

and so on.

any solution/Idea in o(n) or o(nLogn) ?

anucode
6 months ago
8

Comments (8)

Write comment?

sancxo.

6 months ago, # |

← Rev. 2 →

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class SegmentTree {
private:
    vector<int> tree;
    int n;

    void buildTree(const vector<int>& nums, int node, int start, int end) {
        if (start == end) {
            tree[node] = nums[start];
        } else {
            int mid = (start + end) / 2;
            buildTree(nums, 2 * node, start, mid);
            buildTree(nums, 2 * node + 1, mid + 1, end);
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }

    void update(int node, int start, int end, int index, int val) {
        if (start == end) {
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            if (index >= start && index <= mid) {
                update(2 * node, start, mid, index, val);
            } else {
                update(2 * node + 1, mid + 1, end, index, val);
            }
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }

    int query(int node, int start, int end, int left, int right) {
        if (left > right) return 0;
        if (left == start && right == end) return tree[node];
        int mid = (start + end) / 2;
        return query(2 * node, start, mid, left, min(right, mid)) +
               query(2 * node + 1, mid + 1, end, max(left, mid + 1), right);
    }

public:
    SegmentTree(const vector<int>& nums) {
        n = nums.size();
        tree.resize(4 * n);
        buildTree(nums, 1, 0, n - 1);
    }

    void update(int index, int val) {
        update(1, 0, n - 1, index, val);
    }

    int query(int index) {
        return query(1, 0, n - 1, 0, index);
    }
};

vector<int> oddIndexSum(const vector<int>& nums) {
    int n = nums.size();
    SegmentTree segmentTree(vector<int>(n, 0));
    vector<int> result;

    for (int i = 0; i < n; ++i) {
        if (i % 2 == 0) {
            result.push_back(segmentTree.query(i / 2));
        } else {
            segmentTree.update(i / 2, nums[i]);
        }
    }

    return result;
}

int main() {
    vector<int> nums = {3, 1, 5, 2, 4, 6, 8, 7};
    vector<int> result = oddIndexSum(nums);
    for (int sum : result) {
        cout << sum << " ";
    }
    cout << endl;
    return 0;
}

→ Reply

anucode

6 months ago, # ^ |

← Rev. 2 →

plzz explain that code just introduction

→ Reply

ishwarendra

6 months ago, # |

← Rev. 2 →

This can be solved without any special data structure. Assume $$$0$$$ based indexing. At index $$$i$$$ you want $$$\lfloor \frac{i}{2} \rfloor$$$ smallest numbers.

You can maintain two multisets $$$\texttt{S}$$$ and $$$\texttt{B}$$$. In $$$\texttt{S}$$$ we will be store smaller numbers while in $$$\texttt{B}$$$ we will store the bigger elements More formally, minimum element of $$$\texttt{B}$$$ should be greater than equal to maximum element of $$$\texttt{S}$$$.

If you notice carefully then you will see that we want to keep lengths of $$$\texttt{S}$$$ and $$$\texttt{B}$$$ as close as possible with $$$\texttt{B}$$$ having bigger size than $$$\texttt{S}$$$ if you cannot keep the sizes equal. At each step you can decide whether you want to put element in $$$\texttt{S}$$$ or $$$\texttt{B}$$$ by first filling the multiset with smaller size and then until you find $$$\textbf{Maximum element of}$$$ $$$\texttt{S}$$$ > $$$\textbf{Minimum element of}$$$ $$$\texttt{B}$$$. You can keep track of the sum of elements present in $$$\texttt{S}$$$ easily.

Code Snippet

#include "bits/stdc++.h"

using i64 = long long;

int main()
{
    int n;
    std::cin >> n;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++)  
        std::cin >> a[i];
    
    std::multiset<int> S, B;
    i64 minSum = 0;
    auto add = [&](int x)
    {
        if (std::size(S) < std::size(B))
            S.emplace(x), minSum += x;
        else
            B.emplace(x);
        
        if (S.empty())
            return;
        
        while (true)
        {
            // if max element of S > min element of B swap them
            // otherwise everything is ok
            int maxS = *std::prev(std::end(S));
            int minB = *std::begin(B); 
            
            if (minB >= maxS)
                break;
            
            S.erase(std::prev(std::end(S)));
            minSum -= maxS;
            
            B.erase(std::begin(B));
            
            S.emplace(minB);
            minSum += minB;
            
            B.emplace(maxS);
        }
    };
    
    i64 pref = 0;
    std::vector<i64> ans(n);
    for (int i = 0; i < n; i++)
    {
        pref += a[i];
        add(a[i]);
        
        if (i % 2)
            continue;
        
        ans[i] = minSum;
    }

    for (int i = 0; i < n; i += 2)
        std::cout << ans[i] << " ";
    std::cout << "\n";
}

→ Reply

anucode

6 months ago, # ^ |

Thanks

→ Reply

a_gt3_rs

6 months ago, # |

← Rev. 3 →

Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename X>
using setx = tree<X, null_type, less<X>, rb_tree_tag,
                  tree_order_statistics_node_update>;
const int N = 1e5; // limit for array size
int n;             // array size
int t[2 * N];
void modify(int p, int value)
{ // set value at position p
    for (t[p += n] = value; p > 1; p >>= 1)
        t[p >> 1] = t[p] + t[p ^ 1];
}
int query(int l, int r)
{ // sum on interval [l, r)
    int res = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1)
    {
        if (l & 1)
            res += t[l++];
        if (r & 1)
            res += t[--r];
    }
    return res;
}
int main()
{
    cin >> n;
    vector<int> a(n);
    vector<pair<int, int>> a_sorted;
    for (auto &i : a)
    {
        cin >> i;
        a_sorted.push_back({i, &i - &a[0]});
    }
    sort(a_sorted.begin(), a_sorted.end());
    vector<int> orders(n);
    for (int i = 0; i < n; i++)
    {
        orders[a_sorted[i].second] = i;
    }
    setx<int> orderset;
    vector<int> odd_sums;
    for (int j = 0; j < n / 2; j++)
    {
        for (int i = 2 * j; i <= 2 * j + 1; i++)
        {
            orderset.insert(orders[i]);
            modify(orders[i], a[i]);
        }
        auto it = orderset.find_by_order((orderset.size() - 1) / 2);
        odd_sums.push_back(query(0, (*it)));
    }
    for (auto i : odd_sums)
        cout << i << " ";
    cout << endl;
}

Algorithm

→ Reply

anucode

6 months ago, # ^ |

Thanks it was helpful.

→ Reply

md_nihal

6 months ago, # |

submission

→ Reply

anucode

6 months ago, # ^ |

Thanks

→ Reply