单点修改、区间求和（模板）、区间修改，单点查询（模板）
题目描述
一行 NN 个方格，开始每个格子里都有一个整数。
你需要动态地进行一些操作，操作有以下两种类型：
- 提问：求某一个特定的子区间 [a,b][a,b] 中所有元素的和；
- 修改：指定某一个格子 xx，令 xx 加上或者减去一个特定的值 AA。
现在要求你能对每个提问作出正确的回答。
输入描述
输入文件第一行为一个整数 NN，接下来一行包含 nn 个整数，表示格子中原来的整数。
接下一个正整数 mm，再接下来有 mm 行，表示 mm 个询问。每个询问的第一个整数表示询问代号，询问代号 11 表示增加，后面的两个数 xx 和 AA 表示给位置 XX 上的数值增加 AA ，询问代号 22 表示区间求和，后面两个整数表示 aa 和 bb ，表示要求 [a,b][a,b] 之间的区间和。
1≤N,X,A≤100000，m≤100001≤N,X,A≤100000，m≤10000。
输出描述
共 mm 行，每行一个整数，表示每个提问的答案。
输入输出样例
示例
输入
6 4 5 6 2 1 3 4 1 3 5 2 1 4 1 1 9 2 2 6输出
22 22树状数组
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N = 100010; static long c[]=new long[N]; static int a[]=new int[N]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine()); String g[] = br.readLine().split(" "); for (int i = 1; i <= n; i++) { add(i, Integer.parseInt(g[i-1]), n); } int m=Integer.parseInt(br.readLine()); for (int i = 0; i < m; i++) { g = br.readLine().split(" "); int op=Integer.parseInt(g[0]),a=Integer.parseInt(g[1]),b=Integer.parseInt(g[2]); if(op==1){ add(a,b,n);//添加类似于单点修改 }else{ long sum=query(b); long sum1=query(a-1); System.out.println(sum-sum1); } } } static int lowbit(int x){ return x & -x; } static void add(int x,int v,int n){ for (int i = x; i <= n; i+=lowbit(i)) { c[i]+=v; } } static long query(int a){ long res=0; for (int i = a; i >= 1; i-=lowbit(i)) { res+=c[i]; } return res; } }线段树
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N = 4*100010;//大小一般为4*N static long tree[]=new long[N]; static int a[]=new int[N]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine()); String g[] = br.readLine().split(" "); for (int i = 1; i <= n; i++) { a[i]=Integer.parseInt(g[i-1]); } build(1,1,n); int m=Integer.parseInt(br.readLine()); for (int i = 0; i < m; i++) { g = br.readLine().split(" "); int op=Integer.parseInt(g[0]),x=Integer.parseInt(g[1]),y=Integer.parseInt(g[2]); if(op==1){ update(1,1,n,x,y); }else{ long res=query(1,1,n,x,y); System.out.println(res); } } } static long query(int id,int l,int r,int ql,int qr){ if(l>=ql&& r<=qr){ return tree[id]; } int mid=(l+r)>>1; long res=0; if(ql<=mid)res+=query(2*id, l, mid, ql, qr); if(qr>=mid+1)res+=query(2*id+1, mid+1, r, ql, qr); return res; } static void update(int id,int l,int r,int pos,int x){ if(l==r){ tree[id]+=x; return; } int mid=(l+r)>>1; if(pos<=mid)update(2*id, l, mid, pos, x); else update(2*id+1, mid+1, r, pos, x); pushup(id); } static void pushup(int id){ tree[id]=tree[2*id]+tree[2*id+1]; } static void build(int id,int l,int r){ if(l==r){ tree[id]=a[l]; return; } int mid=(l+r)>>1; build(2*id, l, mid); build(2*id+1, mid+1, r); pushup(id); } }区间修改，单点查询（模板）
问题描述
给定一个长度为 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.IOException; import java.io.InputStreamReader; public class Main { static int N = 2*100010; static long c[]=new long[N]; static int a[]=new int[N]; static int d[]=new int[N];//给差分数组建立树状数组 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String g[] = br.readLine().split(" "); int n=Integer.parseInt(g[0]),m=Integer.parseInt(g[1]); g = br.readLine().split(" "); for (int i = 1; i <= n; i++) { a[i]=Integer.parseInt(g[i-1]); d[i]=a[i]-a[i-1]; } for (int i = 1; i <= n; i++) { add(i,d[i],n); } // 1 l r x：将l - r的所有数字增加 x。 // 2 idx：输出当前 a{idx} 的值。 for (int i = 0; i < m; i++) { g = br.readLine().split(" "); if(g.length==4){ int l=Integer.parseInt(g[1]),r=Integer.parseInt(g[2]),x=Integer.parseInt(g[3]); add(l,x,n);add(r+1,-x,n); }else{ int idx=Integer.parseInt(g[1]); int res=query(idx); System.out.println(res); } } } static int query(int idx){ int res=0; for (int i = idx; i>=1; i-=lowbit(i)) { res+=c[i]; } return res; } static void add(int pos,int x,int n){ for (int i = pos; i <= n; i+=lowbit(i)) { c[i]+=x; } } static int lowbit(int x){ return x & -x; } }import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N = 4*200010; static int tree[]=new int[N]; static int a[]=new int[N]; static int d[]=new int[N];//给差分数组建立线段树 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String g[] = br.readLine().split(" "); int n=Integer.parseInt(g[0]),m=Integer.parseInt(g[1]); g = br.readLine().split(" "); for (int i = 1; i <= n; i++) { a[i]=Integer.parseInt(g[i-1]); d[i]=a[i]-a[i-1]; } build(1,1,n); // 1 l r x：将l - r的所有数字增加 x。 // 2 idx：输出当前 a{idx} 的值。 for (int i = 0; i < m; i++) { g = br.readLine().split(" "); if(g.length==4){ int l=Integer.parseInt(g[1]),r=Integer.parseInt(g[2]),x=Integer.parseInt(g[3]); update(1,1,n,l,x);if(r+1<=n)update(1,1,n,r+1,-x); }else{ int idx=Integer.parseInt(g[1]); int res=query(1,1,n,1,idx); System.out.println(res); } } } static int query(int id,int l,int r,int ql,int qr) { if(l>=ql && r<=qr){//区间完全包含 return tree[id]; } int mid=(l+r)>>1; int res=0; if(ql<=mid)res+=query(2*id, l, mid, ql, qr); if(qr>=mid+1)res+=query(2*id+1, mid+1, r, ql, qr); return res; } static void update(int id,int l,int r,int pos,int x){ if(l==r){ tree[id]+=x; return; } int mid=(l+r)>>1; if(pos<=mid)update(2*id, l, mid, pos, x); else update(2*id+1, mid+1, r, pos, x); pushup(id); } static void build(int id,int l,int r){ if(l==r){ tree[id]=d[l]; return; } int mid=(l+r)>>1; build(2*id, l, mid); build(2*id+1, mid+1, r); pushup(id); } static void pushup(int id){ tree[id]=tree[2*id]+tree[2*id+1]; } }