Да. В дополнительном массиве можно использовать два зарезервированных значения. Первое - взять значение из суммы на отрезке [l,r], второе - продолжать спуск ниже.
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++);
}