Настройки поиска

struct segment_tree
{
    int n;
    std::vector<int> data;
    std::vector<int> values;
    std::vector<int> etalon;

    segment_tree(const std::vector<int>& array)
    {
        etalon = array; // DEBUG

        n = 1;
        while(n < (int)array.size())
            n <<= 1;

        data.assign(2*n, 0);
        values.assign(2*n, 0);

        for(int i = 0; i < (int)array.size(); ++i)
            data[i+n] = array[i];

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

    void test(int block)
    {
        std::cout << "Running Test Block #" << block << "\n\n";

        int t = 0;
        for(int i = 0; i < (int)etalon.size();++i)
        {
            for(int j = i; j < (int)etalon.size(); ++j)
            {
                t++;

                int sum = get_sum(i,j), sum_etalon = get_sum_etalon(i, j);

                char buf[0xff]={0};
                sprintf(buf, "%02d", t);
                if (sum != sum_etalon)
                    std::cout << "Test #" << buf << " FAILED!\n";
                else
                    std::cout << "Test #" << buf << " PASSED!\n";

            }
        }

        std::cout << "\n";
    }

    int get_sum_etalon(int l, int r)
    {
        int sum_etalon = 0;
        for(int k = l; k <= r; ++k)
            sum_etalon += etalon[k];

        return sum_etalon;
    }

    int get_sum(int l, int r)
    {
        return get_sum(1, 0, n-1, l, r);
    }

    int get_sum(int root, int left, int right, int l, int r)
    {
        if (values[root] > 0)
            return values[root]*(r-l+1);

        if (l == left && r == right && values[root] != -1)
            return data[root];

        int sum = 0;

        int right_dash = (right+left)/2, left_dash = (right+left)/2+1;
        if (l <= right_dash)
            sum += get_sum(root*2, left, right_dash, l, std::min<int>(r, right_dash) );

        if (r >= left_dash)
            sum += get_sum(root*2+1, left_dash, right, std::max<int>(left_dash, l), r);

        return sum;
    }

    void set_value(int l, int r, int value)
    {
        set_value_etalon(l, r, value);
        set_value(1, 0, n-1, l, r, value);
    }

    void set_value_etalon(int l, int r, int value)
    {
        for(int k = l; k <= r; ++k)
            etalon[k] = value;
    }

    void set_value(int root, int left, int right, int l, int r, int value)
    {
        if (l == left && r == right)
        {
            values[root] = value;
            return;
        }

        if (values[root] > 0)
            values[root*2 + 1] = values[root*2] = values[root];
        
        values[root] = -1;

        int right_dash = (right+left)/2, left_dash = (right+left)/2+1;
        if (l <= right_dash)
            set_value(root*2, left, right_dash, l, std::min<int>(r, right_dash), value);

        if (r >= left_dash)
            set_value(root*2+1, left_dash, right, std::max<int>(left_dash, l), r, value);
    }
};


int main(int argc, char* argv[])
{
    int data[] = {1,2,3,4,5,6,7,8,9};
    std::vector<int> arr(data, data+sizeof(data)/sizeof(data[0]));
    segment_tree st(arr);

    int t = 1;
    st.test(t++);

    st.set_value(0, 6, 4);
    st.test(t++);

    st.set_value(1, 4, 6);
    st.test(t++);

    st.set_value(2, 8, 5);
    st.test(t++);

}