The problem of interval summation -- difference

• The array doesn't change , Interval query ： The prefix and 、 Tree array 、 Line segment tree ;
• Single point modification of array , Interval query ： Tree array 、 Line segment tree ;
• Array interval modification , Single point query ： Difference 、 Line segment tree ;
• Array interval modification , Interval query ： Line segment tree .

Be careful ： The above summary is for general purposes （ Can be solved directly ）, The benchmark is the template problem . But there are some processes “ additional ” operation , Transform the problem , So as to solve the problem with other solutions .

For example, some problems , We can first make a difference to the original array , Then use the tree array , It can also solve the interval modification problem .

Or use multiple tree arrays to maintain multiple indicators , So as to realize the persistent marking operation similar to the segment tree .

Gongshui Sanye Introduction topic analysis