#include <iostream>
#include <vector>
#include <cmath>


//       i: 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15  size = 2*n
//  vec[i]: 3  1  4  1  5  9  2  6
// tree[i]: 0 31  9 22  4  5 14  8  3  1  4  1  5  9  3  6
//     sum:               +5+14       +1             +2     = 22
//
//                 31 
//              9      22                      sum: O(log n)
//            4   5  14   8                 update: O(log n)
//           3 1 4 1 5 9 2 6  
//
//          n' = 2^ceil(log(n))     (Prvi stepen dvojke >= n)

class SegmentTree
{
public:
    SegmentTree(const std::vector<int> &vec) 
    {
        int n = std::pow(2, std::ceil(std::log2(vec.size())));

        m_tree = std::vector<int>(2 * n);

        for (int i = 0; i < n; i++) {
            m_tree[n + i] = vec[i];
        }

        for (int i = n - 1; i > 0; i--) {
            m_tree[i] = m_tree[2 * i] + m_tree[2 * i + 1];
        }
    }

    int sum(int l, int r) 
    {
        const int n = m_tree.size() / 2;

        int sum = 0;
        l = n + l; r = n + r;
        while (l < r) {
            if (l % 2 != 0) sum += m_tree[l++];
            if (r % 2 == 0) sum += m_tree[r--];
            l /= 2; r /= 2;
        }

        return sum;
    }

    void update(const int i, const int value)
    {
        int k = m_tree.size() / 2 + i;

        m_tree[k] = value;
        k /= 2;
        while (k > 0) {
            m_tree[k] = m_tree[2 * k] + m_tree[2 * k + 1];
            k /= 2;
        }
    }

    ~SegmentTree() {}

private:
    std::vector<int> m_tree; 
};

int main(void)
{
    std::vector<int> vec = { 3, 1, 4, 1, 5, 9, 2, 6 };

    auto segment_tree = new SegmentTree(vec);

    std::cout << segment_tree->sum(1, 6) << std::endl;

    segment_tree->update(6, 3);

    std::cout << segment_tree->sum(1, 6) << std::endl;
    
    delete segment_tree;

    return 0;
}