差分法(面试重要！important)

本文主要是介绍差分法(面试重要！important)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/contest/10323/A
来源：牛客网

牛牛现在在花园养了n棵树，按顺序从第1棵到第n棵排列着。牛牛每天会按照心情给其中某一个区间的树浇水。例如如果某一天浇水的区间为[2,4]，就是牛牛在这一天会给第2棵，第3棵和第4棵树浇水。树被浇水后就会成长，为了简化问题，我们假设在初始时所有树的高度为0cm。每过去一天树会自然成长1cm，每次树被浇水后当天会额外成长1cm。m天中牛牛每天都都会选一个区间[l,r]对这个区间内的树进行浇水，牛牛想知道m天后有多少棵树的高度为奇数，你能告诉牛牛吗？
示例1
输入
复制
3,2,[1,2],[2,3]
返回值
复制
2
说明
第一天后第一棵树高度为2，第二棵树高度为2，第三棵树高度为1
第二天后第一棵树高度为3，第二棵树高度为4，第三棵树高度为3，一共两棵树高度为奇数，所以输出2

思路:
在这里插入图片描述差分来模拟+1的操作很棒

import java.util.*;
public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可* 返回m天后高度为奇数的树的数量* @param n int整型 * @param m int整型 * @param l int整型一维数组 * @param r int整型一维数组 * @return int整型*/static int[] sum = new int[200020];public int oddnumber (int n, int m, int[] l, int[] r) {// write code hereint i;for(i = 0; i < m; i++) {sum[l[i]]++;sum[r[i]+1]--;}for(i = 1; i <= n; i++){sum[i] = sum[i-1] + sum[i];}int res = 0;for(i = 1; i <= n; i++) {if((sum[i] + m) % 2 == 1){res++;}}return res;}
}