区间修改，单点查询（模板）（差分构建）

区间修改单点查询模板问题描述给定一个长度为 nn 的序列 aa你需要进行 mm 次操作每次操作为以下两种之一1 l r x将 al∼ral∼r​ 的所有数字增加 xx。2 idx输出当前 aidxaidx​ 的值。输入格式第一行输入两个正整数 n,mn,m。(1≤n,m≤2×105)(1≤n,m≤2×105)第二行输入 nn 个正整数 aiai​。(1≤ai≤104)(1≤ai​≤104)接下来 mm 行每行输入代表一种操作。1 l r x将 al∼ral∼r​ 的所有数字增加 xx。2 idx输出当前 aidxaidx​ 的值。(1≤l≤r≤n,1≤x≤103,1≤idx≤n)(1≤l≤r≤n,1≤x≤103,1≤idx≤n)输出格式对于每次操作 22输出对应的答案。样例输入3 2 1 2 3 1 1 3 1 2 2样例输出3树状数组实现import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N2*100010; static long c[]new long[N];//树状数组 static int a[]new int[N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); int mInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); } for (int i 1; i n; i) { add(i,a[i]-a[i-1]); } //我们可以对原数组的差分数组维护一个树状数组 这样区间修改两个单点修改 //单点查询就变成了区间查询 for (int i 0; i m; i) { stnew StringTokenizer(br.readLine()); int opeInteger.parseInt(st.nextToken()); if(ope1){ int lInteger.parseInt(st.nextToken()),rInteger.parseInt(st.nextToken()),xInteger.parseInt(st.nextToken()); add(l,x); add(r1,-x); }else{ int idxInteger.parseInt(st.nextToken()); bw.write(query(idx)\n); } } br.close(); bw.flush(); bw.close(); } static int lowbit(int x){ return x-x; } static void add(int x,int k){ for (int i x; i n; ilowbit(i)) { c[i]k; } } static int query(int x){ int sum0; for (int i x; i 0; i-lowbit(i)) { sumc[i]; } return sum; } }线段树实现import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N2*100010; static int tree[]new int[4*N];//线段树 static int a[]new int[N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); int mInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); } for (int i 1; i n; i) { add(1,1,n,i,a[i]-a[i-1]); } //我们可以对原数组的差分数组维护一个线段树 这样区间修改两个单点修改 //单点查询就变成了区间查询 for (int i 0; i m; i) { stnew StringTokenizer(br.readLine()); int opeInteger.parseInt(st.nextToken()); if(ope1){ int lInteger.parseInt(st.nextToken()),rInteger.parseInt(st.nextToken()),xInteger.parseInt(st.nextToken()); add(1,1,n,l,x); if(r1n)add(1,1,n,r1,-x);//注意加判断语句 }else{ int idxInteger.parseInt(st.nextToken()); bw.write(query(1,1,n,1,idx)\n); } } br.close(); bw.flush(); bw.close(); } static int query(int id,int l,int r,int x,int y){ if(lx ry){ return tree[id]; } int mid(lr)1; int res0; if(xmid)resquery(2*id, l, mid, x, y); if(ymid1)resquery(2*id1, mid1, r, x, y); return res; } static void add(int id,int l,int r,int x,int k){ if(lr){ tree[id]k; return; } int mid(lr)1; if(xmid)add(2*id, l, mid, x, k); else add(2*id1, mid1, r, x, k); pushup(id); } static void pushup(int id){ tree[id]tree[2*id]tree[2*id1]; } }