### anucode's blog

By anucode, history, 5 weeks ago,

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) ?

• +5

 » 5 weeks ago, # | ← Rev. 2 →   0 Code#include #include #include using namespace std; class SegmentTree { private: vector tree; int n; void buildTree(const vector& 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& 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 oddIndexSum(const vector& nums) { int n = nums.size(); SegmentTree segmentTree(vector(n, 0)); vector 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 nums = {3, 1, 5, 2, 4, 6, 8, 7}; vector result = oddIndexSum(nums); for (int sum : result) { cout << sum << " "; } cout << endl; return 0; } 
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 plzz explain that code just introduction
 » 5 weeks ago, # | ← Rev. 2 →   +3 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 a(n); for (int i = 0; i < n; i++) std::cin >> a[i]; std::multiset 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 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"; } 
•  » » 5 weeks ago, # ^ |   0 Thanks
 » 5 weeks ago, # | ← Rev. 3 →   0 Code#include #include #include #include #include using namespace std; using namespace __gnu_pbds; template using setx = tree, 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 a(n); vector> a_sorted; for (auto &i : a) { cin >> i; a_sorted.push_back({i, &i - &a[0]}); } sort(a_sorted.begin(), a_sorted.end()); vector orders(n); for (int i = 0; i < n; i++) { orders[a_sorted[i].second] = i; } setx orderset; vector 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; }  AlgorithmWe first convert the numbers to their orders, then find which order corresponds to the i/2 th element, then get the sum of all numbers < that number (from the orders) in the first i+1 elements of the array (some orders are not filled yet, so the value is 0) (Since the query() function processes half-intervals, its "<" and not "<=" as expected).
•  » » 5 weeks ago, # ^ |   0 Thanks it was helpful.
 » 5 weeks ago, # |   0 submission https://www.codechef.com/viewsolution/1060437598You can see solution, it's the same problem
•  » » 5 weeks ago, # ^ |   0 Thanks