CSUBQ - Editorial

Author: Deepjal Chhetri
Tester: Istvan Nagy
Editorialist: Oleksandr Kulkov

MEDIUM

Segment trees

PROBLEM:

You are to answer the following queries on an array (initially, all elements are zero):

1. 1 x y - Change x'th element to y
2. 2 l r - Count the number of subarrays [l_1, r_1] of subarray [l, r] (that is, l\le l_1\le r_1\le r), whose maximum element lies in range [L, R]. Numbers L and R are the same in all queries.

QUICK EXPLANATION:

Write the number of subarrays whose maximum element lies in the range [L, R] as:

|\{\text{subarrays with max}\in[L,R]\}|=|\{\text{subarrays with max} < R+1\}|-|\{\text{subarrays with max} < L\}|

Observe that:

|\{\text{subarrays with max} < X\}|=|\{\text{subarrays with all elements} < X\}|

For X=L and X=R+1, maintain an array whose element at position i is 0 if a[i]\ge X and 1 if a[i] < X. The query 2 now reduces to: “count number of subarrays on segment [l,r] consisting entirely of ones”. This new problem can be solved using segment tree.

EXPLANATION:

Refer to the “Quick explanation” section for the first part of the solution. The problem is now reduced to answering the following queries for fixed X:

1. 1 x y - Change x'th element to y (y\in\{0, 1\})
2. 2 l r - Count the number of subarrays [l_1, r_1] of subarray [l, r] (that is, l\le l_1\le r_1\le r) consisting of 1's. Number X is the same in all queries.

Use segment tree to solve this problem. In each node, store the following information:

struct Node {
long long num_ones_subarrays;
int len, len_ones_left, len_ones_right;
};


Here,

1. len is the length of the range [l;r] represented by the node (len=r-l+1)
2. num_ones_subarrays is the number of subarrays consisting of ones in the range represented by the node
3. len_ones_left is the length of the largest prefix consisting of ones in the range represented by the node
4. len_ones_right is the length of the largest suffix consisting of ones in the range represented by the node

In order to solve the problem we should show that the stored information is self-sufficient, that is, we can merge two nodes and recalculate all 4 variables. So, suppose that nodes a and b are being merged into node res. Then:

1. Length of res range is the sum of lengths of ranges a and b.
2. The number of ones subarrays in the res range can be calculated as the sum of number of subarrays lying completely in a range (a.num_ones_subarrays), in b range (b.num_ones_subarrays) and the number of subarrays that cross the boundary between a and b. As the subarrays should be non-empty and should consist of ones, it is a.len_ones_right\times b.len_ones_left.
3. The length of the largest prefix of ones in the res range is len_ones_left if there is at least one zero in the range a, that is, if a.len_ones_left \neq a.len. Otherwise, it is a.len_ones_left+b.len_ones_left.
4. The length of the largest suffix is computed similarly.

This corresponds to the following Node merge code:

Node merge(Node a, Node b) {
Node res;

res.len = a.len + b.len;

res.num_ones_subarrays =
a.num_ones_subarrays +
b.num_ones_subarrays +
a.len_ones_right * (li)b.len_ones_left;

res.len_ones_left = a.len_ones_left;
if (a.len_ones_left == a.len)
res.len_ones_left += b.len_ones_left;

res.len_ones_right = b.len_ones_right;
if (b.len_ones_right == b.len)
res.len_ones_right += a.len_ones_right;

return res;
}


The time complexity of the solution is O((N+Q)\log N) from the underlying segment tree (it is possible to make it O(N+Q\log N) by building the segment tree in linear time). The memory complexity of the solution is O(N).

The implementation with 2 separate segment trees for different X=L and X=R+1 is enough to get AC, yet it is possible to make it faster via combining the trees into one.

As the input is quite large, care should be taken to avoid unnecessary input lag. For example, using C++ iostreams consider adding:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);


AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

RELATED PROBLEMS:

5 Likes

Nice Editorial for someone who have started learning segment tree.

Can anyone compile list of problems using segment tree of easy and medium difficulty.

2 Likes

https://www.codechef.com/certification/prepare#advanced .Look at the Segment trees (#3) section.Hope this helps :).

1 Like

if coding in c++ avoid using the “new” operator to dynamically create new structs.
the constraints of this Q are hard as it is and you would not be doing any favors by handling dynamic memory.
i ignored the above and paid the price; the price being 3 days spent debugging my code not understanding why 1 test case wasn’t making the time limit cut.
just do “node t” and not “node* t = new node()”
my execution time was cut by half thanks to the above

Great tutorial. Can someone provide with a curated list of resources to learn segment trees from ? Also, questions from beginner level on segment trees would be appreciated. Thank you

Why am I getting WA in my solution for this problem ?

Can anybody tell the reason behind WA for https://www.codechef.com/viewsolution/19364227 .