Point Update
Point-update problems seem to be solvable directly with a Binary Indexed Tree as well. The basic idea is to build the tree first. When updating down to a leaf node, read the data there (note: read left first, then right, to ensure the input order), then process recursively. After the recursion, do not forget PushUp, otherwise the parent's value will not be updated. After the build is complete, write an Update function. The simple approach is: if the position to be updated lies in the left interval, recurse into the left interval; otherwise recurse into the right interval. When reaching the end, directly modify the value and return; otherwise, remember to PushUp after the recursive call completes.
Querying is straightforward: return directly when the interval matches; otherwise recurse to query. Note the different handling for sums / maximums and similar tasks.
Range Update
The essence of range updates is the use of lazy tags. A lazy tag indicates how a node's sub-intervals should have been updated, but when the interval matches exactly we "cut corners" and do not continue updating downward; instead we leave such a tag, hence the name lazy tag. This description also reflects the nature of lazy tags: they are only operated on during PushDown.
In the Update function, when the interval matches exactly, thanks to lazy tags we can "cut corners" by only updating this matched interval, recording the lazy tag, and then returning. Clearly, PushDown is only needed when we must update or query child intervals. Because earlier we "cut corners" and did not propagate the information to children, but now we need children's information or need to modify children, we perform PushDown to propagate the update. After propagating, we naturally remove the parent's lazy tag, because we are no longer "cutting corners" at this level—the information has been pushed down.
After finishing the recursive updates on child intervals, we need a PushUp operation to recompute the parent's new information, because we only modified children and must fix the parent during backtracking. At this point we do not need to care about lazy tags, because all lazy tags along the path from top to bottom have been cleared, and the true values will be updated back from bottom to top. During updates, if it is a sum-type update, just set the parent interval's value to the sum of the two child intervals; if two kinds of types need to be merged (possibly the same or different), then when the types differ we should mark with a special value, indicating that the two child intervals under this parent have different tags, so that Query knows it must continue recursing downward.
By the same reasoning, during Query we also need to pay attention to PushDown, because we need children's information. We just do not need PushUp, because we did not make any new modifications; we only propagated old modifications, so no bottom-up update is needed.
For range assignment (replacement) operations when handling coordinate discretization, there is one point that needs special attention: since a segment tree essentially records segments rather than integer endpoints, if you discretize only the endpoints directly, you may end up with under-coverage. For example, after covering intervals [1,4], [1,3], and [4,5], if you add a segment [1,5], then in fact this segment covers all three earlier ones. Therefore, to allow the segment tree to handle this correctly, in such cases you can simply multiply coordinate values by 2. Besides that, range assignment and range add/subtract are essentially the same: one records an increment, the other records an assignment value.
In addition, there is a special classic type of range-update problem: asking for the number of "different elements in an interval", i.e., the coloring problem. For example, POJ_2528 asks how many different kinds of elements exist in the entire interval. If the data range is large, you should first consider discretization; but it is easy to make mistakes during discretization, so you need some extra processing on the sorted array. For instance, when the difference between adjacent elements is greater than 1, you should insert an extra element arbitrarily; e.g., [1,2,6,10] can be extended to [1,2,3,6,7,10], and then build the segment tree. During queries, you still perform binary search as usual to map the interval endpoints.
The key to handling this type of problem lies in what information each node records. Here, besides recording the color covering the node, we also record whether this interval is fully covered by a single color (is_FullFilled). For coloring problems with very few possible colors, you can directly use bit operations to record the state. When querying, not only must the interval match, but the interval must also have only one color before you process and return; otherwise continue recursing. During processing, note that you should only count colors that have not appeared before (use a marker array to record the state), then add 1 to the answer and return. It follows that for each query you need to clear the color marker array, which also means that if there are many colors, there cannot be many queries in the problem statement—for example, POJ_2528 has only one query, because the clearing cost is too high.
There is another kind of "different in a range" problem, such as HDU_3333, which asks for the sum of distinct elements in a range. In this case you can no longer use the above approach. Instead, first discretize the values by range (the goal is to shrink the value domain so you can record the position where each element appears); then read in all queries, sort them by the right endpoint, and convert the process into offline handling. Then traverse the elements in order, ensuring that when processing queries with right endpoint r, any element that has appeared must appear only at the rightmost position possible and <= r. Then the sum computed by a segment tree or a Binary Indexed Tree will be the correct answer. The maintenance rule is: if an element has not appeared before, add it at the current position; otherwise, first remove the value at its previous occurrence position, then add it at the current traversed position.
Interval Merging
This type of problem mainly asks for the maximum length of some kind of consecutive elements in an interval. Compared with ordinary range updates, both Update and Query will change somewhat, and the logic of PushUp and PushDown becomes more complex.
For PushDown, the essence is the same as in range updates. If the parent interval has been updated before (not marked as an invalid value), then during PushDown you first save the update value to the child nodes, update the child nodes' information accordingly, and finally remove the parent's update value (mark it invalid), because the parent's value will be recomputed during PushUp. For PushUp, you need to merge several cases that form consecutiveness, updating the interval's left side, right side, and the maximum consecutive length; see the code for details.
With the basic PushUp and PushDown operations above, the subsequent Update is simple: just find the corresponding interval to update. If it is not the target interval, first PushDown, then recurse to update, and finally PushUp.
As for the operation of querying a position, it is a bit more complex. First, determine whether there exists an interval satisfying the condition; this is easy: if the maximum consecutive length recorded at the root for the whole range does not satisfy it, then obviously it cannot be found; otherwise you can recurse. If you reach a leaf node, return the leaf position directly. If the left subtree's maximum length satisfies the required length, query on the left; if the sum of the left subtree's right side and the right subtree's left side satisfies it, compute the corresponding position and return; if none of the above holds, then query the right subtree. In short, once you enter the recursion, you will definitely find one.
Finally, regarding the basic operation of "pushing up from leaf nodes", there are actually many interesting properties to explore. For example, HDU3308 asks for the length of the longest consecutive increasing subsequence in a range that supports arbitrary point updates. This can be transformed into using segment tree properties: based on a fixed sequence, maintain left/right and maximum consecutive lengths by pushing information bottom-up.
Sweep Line
It has been a long time since I last solved a sweep-line problem; leaving a placeholder to fill later.