#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;
}

#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";
}

#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;
}

We 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).

https://www.codechef.com/viewsolution/1060437598

You can see solution, it's the same problem