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

//       i: 0  1  2  3  4  5  6  7
//  vec[i]: 3  1  4  1  5  9  2  6
// comp[i]: 0  0  1  0  0  1  0  1
// tree[i]: 0  3  1  2  0  1  1  1  0  0  1  0  0  1  0  1

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

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

        for (int i = n; i < 2 * n; i++) {
            m_tree[i] = !is_prime(vec[i - n]);
        }

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

    int sum(int a, int b) 
    {
        const int n = m_tree.size() / 2;

        int l = n + a, r = n + b;
        int sum = 0;

        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(int i, int value)
    {
        const int n = m_tree.size() / 2;

        int k = n + i;
        m_tree[k] = !is_prime(value);

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

    ~SegmentTree() {}

private:
    bool is_prime(int n)
    {
        if (n <= 2) return true;

        for (int i = 2; i * i <= n; i++)
            if (n % i == 0) return false;
        
        return true;
    }

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

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

    auto comp = new SegmentTree(vec);

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

    comp->update(6, 4);

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

    delete comp;

    return 0;
}